ABC148 E - Double Factorial

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def f(N):
    if N <= 2:
        return N
    return N * f(N-2)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()

    ret = 0
    i = 10
    while N >= i and N % 2 == 0:
        ret += N // i
        i *= 5
    print(ret)


if __name__ == '__main__':
    main()

考え方

色々手元で動かしながら雰囲気理解

---

N = 1のとき、末尾のゼロはゼロ個、
N = 10のとき、末尾のゼロは1個、
N = 20のとき、末尾のゼロは2個と増えていきます。
実際に末尾のゼロが遷移するか以下の関数で確かめた結果が次の通りです。

def f(N):
    if N <= 2:
        return N
    return N * f(N-2)

N -> 末尾のゼロの個数
20->2
30->3
40->4
50->6
60->7
70->8
80->9
90->10
100->12
200->24
300->37

末尾のゼロの個数から、なんとなく10が出現するたびにゼロの数が増えているような雰囲気があります。
よくよく考えてみると、2と5で掛け算が行われたときにゼロが増えます。
逆に言うと、2と5で割り切ることができる場合のみゼロが増えることがわかります。
さらに、2または5で割り切れる数を比較したとき、5で割り切れる数の方が少ないことは明らかです。
そのため、最小を10とし、10から5倍ずつした値でNが割り切ることができる回数だけゼロが増えます。
ただし、Nが奇数の場合には2で割り切ることが出来ないため、必ず回答はゼロになります。