이 기사에서는 예를 들어 팩토리얼의 16진법 표현에서 주어진 숫자 N의 후미 0을 찾는 문제를 이해할 것입니다.
Input : N = 7 Output : 1 Explanation : fact(7) = 5040 in base10 and 13B0 in base16 having 1 trailing zero. Input : N = 11 Output : 2 Explanation : fact(11) = 39916800 in base10 and 2611500 in base16 having 2 trailing zeroes.
먼저 십진수를 한 기수에서 다른 기수로 변환하는 과정을 요약해 보겠습니다. (5040)10을 (?)16으로 변환하는 예를 들어보겠습니다.
즉, 숫자를 16으로 나누고 숫자를 더 이상 나눌 수 없을 때까지 나머지를 유지합니다. 결과는 역순으로 나머지가 됩니다.
결과적으로 하나의 후행 0이 있고 이 후행 0은 16이 숫자를 나머지 0으로 나눌 때 얻었습니다.
5040의 소인수 분해 =161 * 451* 71, 즉 16은 5040을 1번 나누고 나머지 0은 후행 0과 같습니다. 이런 식으로 후행 0의 수를 계산할 수 있습니다.
해결책을 찾기 위한 접근 방식
우리는 후행 0의 수를 찾는 방법에 대해 위에서 논의했습니다. 우리는 또한 16 =24를 알고 있습니다. 이는 N의 가장 높은 거듭제곱 2를 4로 나눈 값이 16의 가장 높은 거듭제곱과 같다는 것을 의미합니다. 이것은 르장드르의 공식으로도 알려져 있습니다.
위 접근 방식에 대한 C++ 코드
다음은 주어진 문제를 해결하기 위해 입력으로 사용할 수 있는 C++ 구문입니다 -
예시
#include <bits/stdc++.h>
using namespace std;
int main () {
int n = 11;
long long int count = 0;
long long int value, power = 2;
long long int result;
do{
value = n / power;
count += value;
power *= 2;
}
while (value != 0);
// Count has the highest power of 2
result = count / 4;
cout << "Number of trailing zeroes in base 16 representation of N : " << result;
} 출력
Number of trailing zeroes in base 16 representation of N: 2
위 코드 설명
- 최고의 거듭제곱 2를 계산해야 하므로 거듭제곱을 2로 초기화합니다.
- n을 거듭제곱으로 나누고 count를 값으로 증가시키고 거듭제곱을 2로 하는 while 루프에서 Legendre의 공식을 구현합니다.
- 2의 가장 높은 거듭제곱을 4로 나눈 후 count 변수에 저장됩니다.
- 드디어 결과를 출력하고 있습니다.
결론
이 기사에서는 Legendre 공식을 사용하여 푸는 계승 N의 base16 표현에서 후미 0의 수를 찾는 문제를 해결합니다. 우리는 또한 같은 문제를 해결하기 위해 C++ 코드를 작성합니다. 이 코드는 Java, C, python 등과 같은 다른 언어로 작성할 수 있습니다. 이 문서가 도움이 되기를 바랍니다.