어떤 문제인가?

1676번 문제의 심화 유형. $\begin{pmatrix}n\\k \end{pmatrix}$ 뒤에 있는 0의 개수를 세는 문제.

수가 너무 크다

Wolfram alpha로 $2×10^9!$를 계산하면 자그마치 10의 지수가 10만에 달한다. 정공법으로 풀면 파이썬조차 메모리 초과로 나가떨어진다.

1676번 문제에서 $5^n$으로 나눈 값을 더했다. 이 문제도 원리는 동일하다. 나 또한 유사하게 접근해서 풀었다.

내 코드

import math
k1, k2 = 0, 0
n, m = map(int, input().split())
for i in range(int(math.log(n,2)),0,-1):
    k1 = k1 + int(n/2**i)
if m>0:
    for i in range(int(math.log(m,2)),0,-1):
        k1 = k1 - int(m/2**i)
if n-m > 0:
    for i in range(int(math.log(n-m,2)),0,-1):
        k1 = k1 - int((n-m)/2**i)
for j in range(int(math.log(n,5)),0,-1):
    k2 = k2 + int(n/5**j)
if m>0:
    for j in range(int(math.log(m,5)),0,-1):
        k2 = k2 - int(m/5**j)
if n-m>0:
    for j in range(int(math.log(n-m,5)),0,-1):
        k2 = k2 - int((n-m)/5**j)
print(min(k1, k2))

나는 최댓값을 먼저 결정한 후 이를 바탕으로 빼 나가는 방식으로 풀었다. 내가 다만 3번이나 틀렸던 것은 $\log_{c}{0}$은 정의되어 있지 않음을 깜빡했던 점이다.

남들의 풀이

def count(n, r, d):
    result, x = 0, d
    while x <= n:
        result += n//x - (n-r)//x - r//x
        x *= d
    return result

n, r = map(int, input().split())
print(min(count(n, r, d) for d in [2, 5]))

rapaeljin님의 풀이
-> https://www.acmicpc.net/source/15118501

나는 최댓값을 먼저 결정했지만, 간결한 풀이는 대부분 상향식으로 접근했다. 2, 5부터 시작해서 말이다. 내가 보기에도 이 방식이 가장 낫다.