https://www.acmicpc.net/problem/1676
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
N!을 직접 구해서는 답이 없다.
long long의 범위를 넘어서도 한참 넘어선다.
10이 곱해질 때마다 10을 나누려 해봤지만 이미 25에서 long long 범위를 넘어선다.
아이디어
결국 5가 몇번 곱해지는지만 알면된다.
그 이유를 보면
5의 배수와 5의 배수 사이를 보자
5k 뒤에
5k + 1
5k + 2
5k + 3
5k + 4
5k + 5
이 때 5k + 1과 5k + 2 중 하나는 짝수인데
그럼 저 중의 하나는 무조건 4의 배수이다.
왜냐하면 2(k + 1) 다음 짝수는 2(k + 2)인데 k + 1과 k + 2중 하나는 2의 배수이므로 둘 중 하나는 4의 배수이기 때문이다.
따라서 N!에 5가 하나 곱해지는 동안 2는 최소 3번 곱해진다.
어쩌다 5의 n제곱이 곱해져도 2의 n제곱이 5의 n제곱보다 작으므로
N!에서 5가 곱해져있는 수는 2보다 무조건 더 적다.
따라서 N!이 10의 몇승인지 알고 싶으면 5가 몇번 곱해져있는지만 알면된다.
코드
#include <stdio.h>
int main()
{
int x, i, N, count;
scanf("%d", &N);
count = 0;
for (i = 1; i <= N; i++)
{
x = i;
while (x % 5 == 0)
{
x /= 5;
count++;
}
}
printf("%d", count);
return 0;
}