[더블릿] fac

[더블릿] fac

N!의 끝에서 연속하는 0의 개수를 출력하는문제이다. 단, N! = N * (N-1) * (N-2) . . . * 3 * 2 * 1

예를들어 10! = 3628800 임으로 끝에서 연속하는0의 개수는 2이다.

입력

N이 주어진다. ( 1 <= N <= 1,000,000,000,000,000,000 )

출력

끝에서 연속하는 0의 개수를 출력한다. 단, 숫자가 너무커질수 있으므로 500,000,000,000,000,007로 나눈 나머지 값을 출력한다.

입출력 예

입력 

1

출력

0

입력

10

출력

2

입력

100

출력

24

입력

1422534662

출력

355633660

[풀이]

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120    <--- 1개

6! = 720

7! = 5040

8! = 40320

9! =362880

10! = 3628800   <--- 2개

15! = 1307...000 <--- 3개

20! = 243...0000 <--- 4개

25! =1551..000000 <--- 6개

n!에서 n이 5로 나누어지면 0이 1씩 증가함을 알 수 있다.

n이 25이면 n/5 로 나누어져 5개의 0을 가지고, 추가적으로 25로 또 나누어지기 때문에 한개의 0을 가진다는 점근법을 세울 수 있다.

n이 50이면 50/5로 나누어져 10개의 0을, 추가적으로 50/25로 또 나누어지기 때문에 2개의 0을 가진다고 예측할 수 있다.

for (int i = 1; i <= 25; ++i) {

      cnt += (long long)(num / pow(5, i)) % 500000000000000007;

 }