Just the Facts
N N! 0 1 1 1 2 2 3 6 4 24 5 120 10 3628800
For this problem, you are to write a program that can compute the last non-zero digit of the factorial for N. For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce "2" because 5! = 120, and 2 is the last nonzero digit of 120.
Input
Input to the program is a series of nonnegative integers, each on its own line with no other letters, digits or spaces. For each integer N, you should read the value and compute the last nonzero digit of N!.
Output
For each integer input, the program should print exactly one line of output containing the single last non-zero digit of N!.
Sample Input
1 2 26 125 3125 9999
Sample Output
124828
/*当输入很大，用这个 1.如果在算阶乘时，先抛下5的倍数不乘，那么剩下的数xi的f(xi)是一个循环： 注意，这里5，10，15……这些数都没有乘上去，所以在那些些位置没有改变。 1 2 3 4 5 6 7 8 9 10 1 2 6 4 4 4 8 4 6 6 11 12 13 14 15 16 17 18 19 20 6 2 6 4 4 4 8 4 6 6 循环：6 2 6 4 4 4 8 4 6 6 （0，1的时候是特例，单独考虑。） 2.出来混，迟早要还的，下面要考虑5的倍数： 5 10 15 20 25 30 35 40 。。。。 提取5以后： 1 2 3 4 5 6 7 。。。 n/5 发现什么了吗？又是一个关于f(n/5)的式子 最终： f(n) = （f(n/5) * 5^(n/5)）* g(n) ; 其中f(n)为n！的最后非零位，g(n)为排除5的倍数时的最后非零位，（f(n/5) * 5^(n/5)） 所有5的倍数乘积的最后非零位。 复杂度log(n),稍微处理一下大数，快的话0 ms。*/ #include<string.h> #include<cstdio> #define MAXN 10000 int lastdigit(char* buf)//f(n) = （f(n/5) * 5^(n/5)）* g(n) { const int mod[20]= {1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}; int len=strlen(buf),a[MAXN],i,c,ret=1; if (len==1) return mod[buf[0]-'0'];//特殊情况 for (i=0; i<len; i++) a[i]=buf[len-1-i]-'0';//字符向数字转换 for (; len; len-=!a[len-1]) { ret=ret * mod[ a[1]%2*10+a[0] ] % 5; for (c=0,i=len-1; i>=0; i--) c=c*10+a[i],a[i]=c/5,c%=5; } return ret+ret%2*5; } int main() { char a[10000]; while(scanf("%s",a)!=EOF) { printf("%d/n",lastdigit(a)); } return 0; }
