이 기사에서는 계승의 기본 B 표현에서 주어진 숫자 N의 후미 0을 찾는 문제를 이해할 것입니다. 예를 들어
Input : N = 7 Base = 2 Output : 4 Explanation : fact(7) = 5040 in base10 and 1001110110000 in base16 having 4 trailing zero. Input : N = 11 Base = 5 Output : 2 Explanation : fact(11) = 39916800 in base10 and 40204314200 in base16 having 2 trailing zeroes.
먼저 십진수를 한 기수에서 다른 기수로 변환하는 프로세스를 요약해 보겠습니다. (5040)10을 (?)2로 변환하는 예를 들어보겠습니다.
즉, 숫자를 2로 나누고 숫자를 더 이상 나눌 수 없을 때까지 나머지를 유지합니다. 결과는 역순으로 나머지가 됩니다.
결과적으로 4개의 후행 0이 있고 이 후행 0은 2가 나머지 0으로 숫자를 나눌 때 얻었습니다.
5040 =24 * 56711 * 3381 * 181의 소인수 분해는 2가 5040을 4번 나누고 나머지 0은 후행 0과 동일함을 의미합니다. 이런 식으로 후행 0의 수를 계산할 수 있습니다.
해결책을 찾기 위한 접근 방식
우리는 후행 0의 수를 찾는 방법에 대해 위에서 논의했습니다. 우리는 계승 N에서 B의 가장 높은 거듭제곱을 찾아야 합니다. 밑수 B =14라고 하면 밑수 14의 14는 10, 즉 (14)10 =(10)14로 표시됩니다. 르장드르의 공식이라고도 합니다.
위 접근 방식에 대한 C++ 코드
다음은 주어진 문제를 해결하기 위해 입력으로 사용할 수 있는 C++ 구문입니다 -
예시
#include <bits/stdc++.h>
using namespace std;
vector < pair < int, int >> primeFactorsofBase(int Base) {
// declaring factors to store prime factors
// along with occurence in factorisation of Base .
vector < pair < int, int >>factors;
for (int i = 2; Base != 1; i++) {
if (Base % i == 0) {
int count = 0;
while (Base % i == 0){
Base = Base / i;
count++;
}
factors.push_back (make_pair (i, count));
}
}
return factors;
}
int main () {
int N = 11, Base = 5;
// finding the largest power of Base that divides factorial N.
vector < pair < int, int >>prime_factors;
// finding prime factors by primeFactorsofBase() function.
prime_factors = primeFactorsofBase(Base);
int result = INT_MAX;
for (int i = 0; i < prime_factors.size (); i++) {
// calculating minimum power.
int count = 0;
int r = prime_factors[i].first;
while (r <= N){
count += (N / r);
r = r * prime_factors[i].first;
}
result = min (result, count / prime_factors[i].second);
}
//printing trailing zeroes stored in result.
cout << "Number of trailing zeroes: " <<result;
return 0;
} 출력
Number of trailing zeroes: 2
위 코드 설명
- 벡터를 사용하여 Base의 가장 큰 거듭제곱을 구합니다.
- 최대 거듭제곱을 계산하려면 모든 소인수를 저장하는 벡터를 사용하여 소인수를 계산합니다.
- 기저의 모든 소인수의 최소 거듭제곱을 계산합니다.
- 마지막으로 결과를 출력합니다.
결론
이 기사에서는 Legendre 공식을 사용하여 푸는 계승 N의 기본 B 표현에서 후미 0의 수를 찾는 문제를 해결합니다. 우리는 또한 같은 문제를 해결하기 위해 C++ 코드를 작성합니다. 이 코드는 Java, C, python 등과 같은 다른 언어로 작성할 수 있습니다. 이 문서가 도움이 되기를 바랍니다.