筆記國度

在這裡放著一些我自己的筆記

[SPOJ] 11. Factorial

| Comments

題目連結:連結

題目

給定一個 ,請算出 的尾端會有幾個

解題報告

因為一個尾端的 是由 所組成,因為 絕對比 還要多,所以只需要算 的數量即可。
所以一開始我寫了一個簡單的除法運算。

for t1 in range(int(input())):
    ia = int(input())
    ans = 0
    while ia>0:
        ia //= 5
        ans += ia
    print(ans)

結果居然噴一個 TLE 給我。
所以我決定建表!
所以程式碼被我改成以下的樣子:

arr1 = dict()
 
def count_5(ia):
    ib = ia//5
    if ib == 0:
        return 0
    if ib not in arr1.keys():
        arr1[ib] = ib + count_5(ib)
    return arr1[ib]
 
for t1 in range(int(input())):
    print( count_5(int(input())) )

結果上傳之後,還是很迅速的噴給我一個 TLE,整個傻眼…看了看題目,時間限制是 6s,看起來應該是其他的原因了。可是,Python 又不像 C++ 一樣,可以把 cin/cout 改用 scanf/printf,於是只好去 Google 找找看,找了一些文章之後,才發現原來很少人用 Python 在解 OnlineJudge,很多地方都是答非所問,囧。後來我終於找到有一篇專門提到 SPOJ 的 Python 如何加速 連結,於是我將程式碼再稍做修改,就成功 Accept 啦。

import sys
arr1 = dict()

def count_5(ia):
    ib = ia//5
    if ib == 0:
        return 0
    if ib not in arr1.keys():
        arr1[ib] = ib + count_5(ib)
    return arr1[ib]

for t1 in range(int(sys.stdin.readline())):
    print( count_5(int(sys.stdin.readline())) )

改天來把找到解答的這個連結看懂好了 :)

Comments

comments powered by Disqus