테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 시파르 ======

===== 풀이 =====
  * [[ps:problems:boj:1676]] 과 같은 문제. [[ps:tutorial:르장드르 공식]]을 이용해서 N!을 소인수분해했을때 5의 지수를 구하면 된다. 시간복잡도는 O(logn)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9693. 시파르".

- Problem link: https://www.acmicpc.net/problem/9693
- Solution link: http://www.teferi.net/ps/problems/boj/9693

Tags: [number theory]
"""

import sys
from teflib import psutils


def exponent_of_prime_in_factorial(n: int, p: int):
    """Compute largest power of a prime p that divides factorial(n)."""
    count = 0
    while n:
        n //= p
        count += n
    return count


@psutils.run_until_all_zero
@psutils.testcase_format('Case #{}: ')
def main():
    N = int(sys.stdin.readline())
    print(exponent_of_prime_in_factorial(N, 5))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_4}}