ACM模版

描述

题解

依稀记得在《具体数学》还是哪本书上有讲到类似这个问题的，不难发现，我们要求的这个最低位，除了 1 ，就只能是偶数了，并且末尾非零位貌似还有什么规律。但是针对于这个问题，大数，如果单纯搞这个规律，貌似并不好做，还需要引入大数运算，但是讨论区大佬说到了一个很精妙的解法，先把 2、5 去掉，分别对 2、5 取余，中国剩余定理合并。

说到这里，让我想到了一个 51Nod 的一个一级题，求阶乘最后 0 的个数，就是对 2、5 进行拆分，因为这两个数的存在必然会构成末尾的 0 ，所以可以去除掉，我们只需要从低位到高位逐渐拆分 2、5 ，并结合前边所提到的末尾非零位的规律即可解决这个问题，不过猛一下还是很难理解这个题究竟怎么写的。

客观讲，这个题我也不是特别会，虽然有了大致的思路但是依然不会解，还是查看了一下大佬们的代码才有所体会，不过我估计下次遇见它，我还是只知道大致思路吧……暂且 Mark 一下吧，数学底子有些差了我。

代码

#include <cstdio>
#include <cstring>

const int MAXN = 10001;
const int MAGIC[] = {
  1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2};

char n[MAXN];
int a[MAXN];

int last_digit()
{
    int len = (int)strlen(n);

    if (len == 1)
    {
        return MAGIC[n[0] - '0'];
    }

    for (int i = 0; i < len; i++)
    {
        a[i] = n[len - 1 - i] - '0';
    }

    int ret = 1;
    while (len)
    {
        ret = ret * MAGIC[a[1] % 2 * 10 + a[0]] % 5;
        for (int c = 0, i = len - 1; i >= 0; i--)
        {
            c = c * 10 + a[i];
            a[i] = c / 5;
            c %= 5;
        }
        len -= !a[len - 1];
    }

    return ret + ret % 2 * 5;
}

int main()
{
    while (scanf("%s", n) != EOF)
    {
        printf("%d\n", last_digit());
    }

    return 0;
}