[請益] 1000000000000!末５位不為０的值要怎求？

[coldnew (夜影)]

這是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
推 LPH66:唔...我用Mathematica暴力跑f(十萬)的答案是62496
→ LPH66:我猜這種方法可能會有奇怪的誤差  像是被你捨去的位數有可能
→ LPH66:會影響答案之類的問題
→ LPH66:舉個簡單的例子 若求末位非0值的話 若只留1位 到15!就錯了
→ LPH66:14!=87178291200 => 2; 15!=1307674368000 => 8
推 ckclark:把5和2都留到最後再算會好一點
→ ckclark:提示 1~10000 去掉5的倍數相乘是 ...09376 其為自守數
推 ckclark:解出來後在討論區可以看到各種神妙解
推 irix2007:16576...我用觀察法發現的. 如前面 LPH66 大大說的,
→ irix2007:會有奇怪誤差. 所以我都是用保留7位來運算
→ irix2007:然後解到100萬時, 每1萬列出結果, 觀察發現差5倍, 後五位
→ irix2007:一樣. 所以一兆的後5位餘數和用2560000來算一樣..
→ irix2007:但我還不知原因..只是運氣好看出這規律
推 SCSonic:這規律可以推測出來的 多點經驗就會往這方面想了
→ coldnew:感謝前輩們的指導^^
→ neverfly:用Java的BigInteger硬幹(逃)
推 powertodream:唔10000! 去掉 5 後五位 09376 是自首數 怎麼發現的?
→ powertodream:所以 一兆的階層 去掉五, 後五位也是 09376
→ powertodream:之後沒做到的5 慢慢算嗎?