[BOJ] 3474 - Factorial

문제 : https://www.acmicpc.net/problem/3474

---

[알고리즘풀이]

정수 K에서 뒤에 붙는 0의 개수는 K를 소인수 분해했을 때, 소수 2와 5로 만들 수 있는 10의 최대 개수랑 같다.

즉, K를 소인수분해했을 때, 2와 5의 개수 중 작은 값이랑 같다.

=> N! 을 소인수 분해했을 때, 2와 5의 개수 중 작은 값을 출력하면 된다.

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n, count_2 = 0, count_5 = 0;
		cin >> n;
		for (int j = 1; ; j++) {
			if ((long long)pow(2, j) <= n)
				count_2 += n / (long long)pow(2, j);
			else
				break;
		}
		for (int j = 1; ; j++) {
			if ((long long)pow(5, j) <= n)
				count_5 += n / (long long)pow(5, j);
			else
				break;
		}
		cout << min(count_2, count_5) << '\n';
	}
}

---