作者coldnew (夜影)
看板Prob_Solve
标题[请益] 1000000000000!末５位不为０的值要怎求？
时间Thu Aug 28 09:51:20 2008
这是Project Euler的160题
题目是这样的：
For any N, let f(N) be the last five digits before the trailing zeroes in N!.
For example,
9! = 362880 so f(9)=36288
10! = 3628800 so f(10)=36288
20! = 2432902008176640000 so f(20)=17664
Find f(1,000,000,000,000)
以下是目前我再run的程式码(Python):
#!/usr/bin/env python
'p160'
from time import time
def fac_cut(n):
tmp=1
if 1==n:return 1
for i in xrange(2,n+1):
tmp=tmp*(int(str(i).strip('0'))%100000)
tmp=int(str(tmp).strip('0'))
tmp%=100000
return tmp
if __name__ == '__main__':
tStart=time()
print '1000000000000! = ', fac_cut(1000000000000)
print 'run time = ' ,str(time()-tStart)
我的想法是这样：
以计算阶乘的方式，tmp*回圈里的i值，当用python的strip（）方法将tmp尾端的0
全部去除，并只取最後５位不为０的数值
回圈里的i值也是一样，当i值尾端有０时，用strip()方法去掉０，并保留末５位不为０
的数值和tmp相乘
目前我的问题是，一兆！实在是太庞大了，我跑到６亿！时用去了我３小时的时间
如此推断，要跑到一兆！要非常久远的时间
曾经想过归纳法，於是我用同样的程式找出如下数值的末端５位非０值：
10! = 36288
100! = 16864
1000! = 53472
10000! = 79008
100000! = 2496
1000000! = 31104
10000000! = 91104
100000000! = 51104
但是一兆！的答案却不是９１１０４，不知道还有什麽方法可以破解此题
请前辈指教
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.244.223
1F：推 LPH66:唔...我用Mathematica暴力跑f(十万)的答案是62496 08/28 12:43
2F：→ LPH66:我猜这种方法可能会有奇怪的误差 像是被你舍去的位数有可能 08/28 12:44
3F：→ LPH66:会影响答案之类的问题 08/28 12:44
4F：→ LPH66:举个简单的例子 若求末位非0值的话 若只留1位 到15!就错了 08/28 12:47
5F：→ LPH66:14!=87178291200 => 2; 15!=1307674368000 => 8 08/28 12:50
6F：推 ckclark:把5和2都留到最後再算会好一点 08/28 14:13
7F：→ ckclark:提示 1~10000 去掉5的倍数相乘是 ...09376 其为自守数 08/28 14:16
8F：推 ckclark:解出来後在讨论区可以看到各种神妙解 08/28 14:39
9F：推 irix2007:16576...我用观察法发现的. 如前面 LPH66 大大说的, 08/28 15:54
10F：→ irix2007:会有奇怪误差. 所以我都是用保留7位来运算 08/28 15:55
11F：→ irix2007:然後解到100万时, 每1万列出结果, 观察发现差5倍, 後五位 08/28 15:56
12F：→ irix2007:一样. 所以一兆的後5位余数和用2560000来算一样.. 08/28 15:59
13F：→ irix2007:但我还不知原因..只是运气好看出这规律 08/28 16:00
14F：推 SCSonic:这规律可以推测出来的 多点经验就会往这方面想了 08/28 16:38
15F：→ coldnew:感谢前辈们的指导^^ 08/28 17:04
16F：→ neverfly:用Java的BigInteger硬干(逃) 08/29 19:03
17F：推 powertodream:唔10000! 去掉 5 後五位 09376 是自首数 怎麽发现的? 08/29 19:24
18F：→ powertodream:所以 一兆的阶层 去掉五, 後五位也是 09376 08/29 19:25
19F：→ powertodream:之後没做到的5 慢慢算吗? 08/29 19:25