详见代码：
方法一：
#include <cstdlib> #include <cstring> #include <cstdio> using namespace std; char s[1005]; int len, Mp[25] = {1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}; // 直接计算出其循环节为20这里将0-19的列表于上，当N<5时直接输出，其余需要递归N/5因为这个表是删除了所有的5的倍数的 int slove() { int ans = 1; while (len) { len -= !s[len-1]; ans = ans * Mp[s[1]%2*10+s[0]] % 10; // Mp中的值就是N%20的值，N%20只与十位和个位有关 for (int i = len-1, t = 0; i >= 0; --i) { // 除以5接着做 t = 10 * t + s[i]; // 其中t为余数 s[i] = t / 5; // num[i]处的商 t %= 5; // 新的余数 } } return ans; } int main() { char t; while (scanf("%s", s) == 1) { len = strlen(s); for (int i = 0, j = len-1; i < (len>>1); ++i, --j) { t = s[i], s[i] = s[j], s[j] = t; } for (int i = 0; i < len; ++i) { s[i] -= '0'; } // 实现交叉以及去字符 printf("%d\n", slove()); } return 0; }
方法二：
#include <cstdlib> #include <cstring> #include <cstdio> #define MAXN 1005 using namespace std; /* 该题思路并没有想着去吧2,5提取出来，如果全部提取出来势必会去计算2的剩余量 由于N很大，所以计算起来要用到两次大数计算除2以及除5后的值再相减再递归下去 而只提取5，把2放入原数列进行计算，最后用除2抵消掉5的影响，这样就可以减少 一次运算了，对于最有一个非零数，由于N!中2的个数始终多余5，所以在有剩余的 情况下，最后这个非零位一定是一个偶数，因此也就能够快速计算出除2之后的结果 了，2/2 = 6 (在不等于1的情况下就只有等于6(12/2)了), 4/2 = 2, 6/2 = 8, 8/2 = 4, 我们就可以建立一个表递归下去了，也就最多抵消4个2，因为除2是有循环 节的。在去除了5的干扰后，我们建立一个按照每10个元素分组的表来表示1*2*3*4*6*7*8*9 的一个非零位{1, 1, 2, 6, 4, 4, 4, 8, 4, 6}，5的倍数{5, 10, 15, 20, 25, 30...} 在提取了5之后构成一个新的序列{1, 2, 3, 4, 5...} 给定一个N我们通过N/10来确定其在 哪一个组，通过N%10来确定其在组内的哪一号元素，通过N/5来确定其递归下去的子序列 注意没有乘以5,10不代表不要统计其位置，我们还是要视作有5的存在，这样在%10计算的 时候才能精确的找到其在一组中的位置，在确定好了其在哪一组的时候，又一个好的性质 帮助了我们，因为每组的最后一个非零位是6，那么组与组进行相乘得到的非零位还是6 所以我们就可以抛弃组数，组数大于1的话直接递归下去乘以6再乘以非零位的精确位置 所存的序列再消去当前序列5的影响就完成了。 F[x] = Mp [ (F[x/5] * 6 * table[x%10])%10 ] [(x/5)%4]，大数的x/5通过乘以2除以10 来得到%4的求解只与一个数的后两位有关 */ char s[MAXN]; int Mp[10][4] = { // 用来记录2,4,6,8分别在除二情况下的非零位变化 {0}, {0}, { 2, 6, 8, 4 }, {0}, {4, 2, 6, 8}, {0}, {6, 8, 4, 2}, {0}, {8, 4, 2, 6}, {0} }; int table[10] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6}; int solve(char *s) { int len, pos, c, k; for (int i = 1003; i >= 0; --i) { if (s[i] != -1) { len = i, pos = s[i]; break; } } if (len == 0) { if (s[0] < 5) return table[s[0]]; else return Mp[table[s[0]]][1]; } else { for (int i = len; i >= 0; --i) { s[i] *= 2; if (s[i+1] >= 10) { s[i] += s[i+1] / 10; s[i+1] %= 10; } } if (s[0] >= 10) { c = s[0] / 10; s[0] %= 10; for (int i = len; i >= 0; --i) { s[i] = s[i-1]; // 向后平移一个距离 } s[0] = c; } else { s[len] = -1; --len; } if (len > 0) { k = s[len] + s[len-1]*10; } else { k = s[len]; } return Mp[(solve(s) * 6 * table[pos])%10][k%4]; } } int main() { memset(s, 0xff, sizeof (s)); while (scanf("%s", s) == 1) { int length = strlen(s); s[length] = -1; for (int i = 0; i < length; ++i) { s[i] -= '0'; } // 化为整数形式 printf("%d\n", solve(s)); memset(s, 0xff, sizeof(s)); } return 0; }