여기에서는 임의의 숫자의 계승 결과에 대해 후행 0의 수를 계산하는 방법을 볼 것입니다. 따라서 n =5이면 5입니다! =120. 뒤에 0이 하나만 있습니다. 20을 위해! 그것은 20으로 4개의 0이 될 것입니다! =2432902008176640000.
가장 쉬운 방법은 계승을 계산하고 0을 계산하는 것입니다. 그러나 이 접근 방식은 n의 큰 값에 대해 실패합니다. 그래서 우리는 다른 접근 방식을 따를 것입니다. 소인수가 2와 5이면 후행 0이 있을 것입니다. 2와 5를 계산하면 결과를 얻을 수 있습니다. 이를 위해 우리는 이 규칙을 따를 것입니다.
후행 0 =factorial(n)의 소인수에서 5의 개수
따라서 후행 0 =$$\lvert\frac{n}{5}\rvert+\lvert\frac{n}{25}\rvert+\lvert\frac{n}{125}\rvert+...$$
이 문제를 해결하려면 다음 단계를 따라야 합니다.
- 세트 수 =0
- i =5, (n/i)> 1, 업데이트 i =i * 5, do
- 카운트 =카운트 + (n /i)
- 반환 횟수
예시(C++)
#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;
int countTrailingZeros(int n) {
int count = 0;
for (int i = 5; n / i >= 1; i *= 5)
count += n / i;
return count;
}
main() {
int n = 20;
cout << "Number of trailing zeros: " << countTrailingZeros(n);
} 입력
Number of trailing zeroes: 20
출력
Number of trailing zeros: 4