BOJ ::1676 팩토리얼 0의 개수 (C++)

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

0은 2와 5의 의해 계산된다. (10 = 2x5)

5의 배수는 2의 배수보다 항상 적으므로 n보다 작은 5의 배수에서 5가 몇번 곱해져있는지 계산하면 된다.

시간을 줄이기 위해,

n을 5의 제곱수만큼 나눠주면 5가 총 몇번 들어있는지 바로 알 수 있다.

ex) 100/5 = 20  (5의 배수가 총 20번)

     100/25 = 4  (25의 배수가 총 4번)

     => 20+4 = 24

 

#include <iostream>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, cnt = 0;
	cin >> n;
	for (int i = 5; i <= n; i*=5) {
		cnt += n / i;
	}
	cout << cnt << "\n";
	return 0;
}