zoj 1222 Just the Facts

最新推荐文章于 2020-02-07 11:05:28 发布

HQD因为有趣所以做题

最新推荐文章于 2020-02-07 11:05:28 发布

阅读量2k

点赞数

分类专栏： ACM_数论文章标签： integer output each input c 2010

本文链接：https://blog.csdn.net/hqd_acm/article/details/6174518

版权

ACM_数论专栏收录该内容

29 篇文章

订阅专栏

本文介绍了一种高效算法，用于计算大数阶乘的最后一非零位数。该算法通过避免直接计算阶乘的方式，显著提高了计算效率，并提供了一个具体的实现示例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Just the Facts

Time Limit: 1 Second Memory Limit: 32768 KB

The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example,

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

1
2
4
8
2
8

/*当输入很大，用这个 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; }