[백준] 1676. 팩토리얼 0의 개수 <C++>

www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

다 곱해보면 long long으로도 표현할 수 없기 때문에 

 

0의 개수를 알 수 있을만한 규칙이 필요하다.

 

우선 뒷자리에 0이 언제 나오는지 알 필요가 있다.

 

5! = 120

5 = 5 * 1

-> 5가 하나 (+1)

0이 1개

 

10! = 3,628,800

10 = 5 * 2

-> 5가 하나 (+1)

0이 2개

 

15! = 1,307,674,368,000

15 = 5 * 3

-> 5가 하나 (+1)

0이 3개

 

20! = 2,432,902,008,176,640,000

20 = 5 * 4

-> 5가 하나 (+1)

0이 4개

 

25! = 15,511,210,043,330,985,984,000,000

25 = 5 * 5

-> 5가 둘 (+2)

0이 6개 

 

 

 

 

5가 몇 번 나왔는지에 따라 0의 개수가 결정된다는 것을 알 수 있다.

 

따라서 5의 개수를 세주면 된다.

 

 

 

 

#include <iostream>
using namespace std;

int main() {
	long long n, _5 = 0;

	cin >> n;
	
	for (int i = 5; i <= n; i *= 5)
		_5 += n / i;

	cout << _5;
}