Factorials 解题报告

题意：求出n！最右侧的非零数字。

我的想法：因为0x任何数均为0，那么每循环一次，就把末尾多余的0去掉。

01 #include <stdio.h>
02 #include <stdlib.h>
03
04 long last(long i)
05 {
06     while(i % 10 == 0)
07         i /= 10;   //删除末尾0
08     return i % 10000;  //防止溢出
09 }
10
11 int main()
12 {
13     long ans,i,n;
14     freopen("fact4.in","r",stdin);
15     freopen("fact4.out","w",stdout);
16     scanf("%ld",&n);
17     for(i = ans = 1;i <= n;i ++)
18     {
19         ans *= i;
20         ans = last(ans);
21     }
22     printf("%ld\n",ans % 10);
23     fclose(stdin);fclose(stdout);
24     return 0;
25 }

官方题解给出了一个适用范围更广的解法：

The insight for this problem is that 0's at the end of a number come from it being divisible by 10, or equivalently, by 2 and 5. Furthermore, there are always more 2s than 5s in a factorial.

To get the last digit of the factorial, we can run a loop to calculate it modulo 10, as long as we don't include any 2s or 5s in the product. Of course, we want to exclude the same number of 2s and 5s, so that all we're really doing is ignoring 10s. So after the loop, we need to multiply in any extra 2s that didn't have 5s to cancel them out.