[請益] 1000000000000!末５位不為０的值要怎求？
這是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
推
08/28 12:43, , 1F
08/28 12:43, 1F
→
08/28 12:44, , 2F
08/28 12:44, 2F
→
08/28 12:44, , 3F
08/28 12:44, 3F
→
08/28 12:47, , 4F
08/28 12:47, 4F
→
08/28 12:50, , 5F
08/28 12:50, 5F
推
08/28 14:13, , 6F
08/28 14:13, 6F
→
08/28 14:16, , 7F
08/28 14:16, 7F
推
08/28 14:39, , 8F
08/28 14:39, 8F
推
08/28 15:54, , 9F
08/28 15:54, 9F
→
08/28 15:55, , 10F
08/28 15:55, 10F
→
08/28 15:56, , 11F
08/28 15:56, 11F
→
08/28 15:59, , 12F
08/28 15:59, 12F
→
08/28 16:00, , 13F
08/28 16:00, 13F
推
08/28 16:38, , 14F
08/28 16:38, 14F
→
08/28 17:04, , 15F
08/28 17:04, 15F
→
08/29 19:03, , 16F
08/29 19:03, 16F
推
08/29 19:24, , 17F
08/29 19:24, 17F
→
08/29 19:25, , 18F
08/29 19:25, 18F
→
08/29 19:25, , 19F
08/29 19:25, 19F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：