[关闭]
@rihkddd 2014-11-25T10:14:20.000000Z 字数 1730 阅读 1037

last no zero digit of N!


结论:

n!的最后一位非零数字,最高效的计算方法是这样的:首先把n转化为5进制数(amam1am2a1a0)5,若f(n!)表示n!的最后一位非零数字,则:

f(n!)2i=0miai×i=0mai!(mod10)

注意:2的幂的最后一位会出现循环节,且这个式子中没有含5的倍数的数出现,因此可以很方便的求出最后一位数字。

思路和简要的证明:

初看结论会感觉到有点神奇,怎么会出现一个5进制呢?公式又看起来好复杂的样子,,最开始分析的时候如果能联想到求n!结尾0的个数问题,你就会意识到n!之所以会产生结尾的0,那是因为里面有一些数是5的倍数,如果除去5的倍数的数,那么我们要找的数字就是乘积最后一个数了,最后一位数字的最多取值0~9,那么这么乘下去必然是会出现循环节的。

思路就是这样,然后形式化一点就可以得出下面的式子:

(5i+1)(5i+2)(5i+3)(5i+4)4(mod10)iZ
因此,如果把n表示为5进制为(amam1am2a1a0)5,则有n=5j+a0
1kn,5kk4j(a0!)(mod10)
f(n!)表示n!的最后一位非零数字,则:
f(n!)f(6jn!)f(6j1kn,5kk1kj5k)(mod10)f30j1kn,5kkj!(mod10)f(3j[4j(a0!)]j!)(mod10)2ja0!f(j!)(mod10)
接着对f(j!)进行相同的推导,这个过程就是把n转化为5进制的过程,而推导的结果恰好就是上面结论中的公式。

附上我的渣代码:

  1. #include <string.h>
  2. #include <stdio.h>
  3. int fact[10]={1,1,2,6,4,6,2,4,8};
  4. char str[1010];
  5. int str10[1500];
  6. int main()
  7. {
  8. while(~scanf("%s",str))
  9. {
  10. if (strcmp(str,"1")>0){
  11. int i,j,prod=1,r=-1,sum=0,mod=0,tem;
  12. int len=strlen(str);
  13. for (i = 0; i < len; ++i) str10[i]=str[i]-'0';
  14. for (i=0; i<len; i+=(!str10[i])){
  15. for (j = i,mod=0; j < len; ++j){
  16. tem=str10[j];
  17. str10[j]=(mod<<1)+(str10[j]>4);
  18. mod=tem%5;
  19. }
  20. sum+=(++r)*mod;
  21. prod=prod*fact[mod]%10;
  22. }
  23. printf("%d\n", fact[sum%4+5]*prod%10);
  24. continue;
  25. }
  26. printf("%d\n",1);
  27. }
  28. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注