DAMPER's blog

www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. www.acmicpc.net N!에서 가장 끝 0의 개수를 세려면 2 * 5의 수를 세면 된다. N!을 소인수분해 했을 때, 2의 개수와 5의 개수를 생각한다면 min(2의 개수, 5의 개수) 가 M인 N! 중 N의 최소값을 찾으면 된다. 2의 개수는 N이 짝수일 때마다 1개 이상 생기고, 5의 개수는 N이 5의 배수일 때마다 1개 이상 생기므로 2의 개수는 항상 5의 개수보다 크거나 같다. 그러므로 5의 개수만 신경쓰자. 그러면 N!에서 5의 개수는 몇개일까? 5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수 + 625의 배수의 개수...