9693 시파르

N!/10^M이 정수라는 이야기는, N! = k * 10^M, 즉 k * 10000...00 (0이 M개)로 나타낼 수 있다는 뜻입니다.

끝자리 0의 개수는 N!의 인수 중 10의 개수로 셀 수 있습니다.

N!을 통째로 계산할 수 없으므로, N! = 1 * 2 * 3 * ... * (N - 1) * N을 이용해서 1부터 N까지의 정수에 대해서 각각 계산하는 방식을 택했습니다.

이 경우에, 10이 각 정수에 나타나지 않아도 N!이 10으로 나누어떨어질 수 있습니다. (5! = 120 = 1 * 2 * 3 * 4 * 5)

10을 소인수분해하면 2 * 5이므로, 우리는 2와 5의 개수를 세어 M을 구할 수 있습니다.

약간의 관찰을 더하면, N!의 인수 중 2의 개수는 항상 5의 개수보다 많음을 알 수 있습니다.

따라서, ((N - 1)!의 인수 중 5의 개수) + (N의 인수 중 5의 개수) 를 통하여 M을 구할 수 있습니다.