ABC148Eを解いた【二重階乗】

筆者はレート800前後の茶～緑コーダ

ABC148のE問題を解いていく

実装コード

与えられた数Nが2で割れる回数と5で割れる回数のどちらか少ない方を求めればいいようで。
公式解説の配信を参考に実装した。

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def g1(n,p):
    if n == 0:return 0
    a = n//p + g1(n//p,p)
    # err(1,n,p)
    # err(a)
    return a

def g2(n,p):
    if n%2 == 1:return g1(n,p) - g2(n-1,p)
    a = g1(n//2,p)
    if p==2: a+= n//2
    # err(2,n,p)
    # err(a)
    return a

def main():
    N = rI()
    n2 = g2(N,2)
    n5 = g2(N,5)
    err(n2)
    err(n5)
    ans = min(n2,n5)
    print(ans)
    
if __name__ == '__main__':
    main()

まとめ

ABC148のE問題を実装した。
二重階乗や割り切れる回数の計算についての実装は難しいが、公式解説が参考になった。