作者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