두 개의 숫자 n과 사실이 있다고 가정합니다. 사실을 나누는 n의 가장 큰 거듭제곱을 찾아야 합니다! (사실의 요인). 따라서 사실 =5이고 n =2이면 출력은 3이 됩니다. 따라서 5입니다! =120이고 2^3 =8로 나눌 수 있습니다.
여기서는 Legendre 공식을 사용합니다. 이것은 사실을 나누는 소수의 가장 큰 거듭 제곱을 찾습니다!. 우리는 n의 모든 소인수를 찾은 다음 사실을 나누는 가장 큰 거듭제곱을 찾습니다.
따라서 사실이 146이고 n =15이면 n의 소인수는 5와 3입니다. 따라서
3의 경우 [146/3] + [48/3] + [16/3] + [5/3] + [1/3] =48 + 16 + 5 + 1 + 0 =70이 됩니다.피>
5의 경우 [146/5] + [29/5] + [5/5] + [1/3] =29 + 5 + 1 + 0 =35가 됩니다.
예
#include<iostream> #include<cmath> using namespace std; int getPowerPrime(int fact, int p) { int res = 0; while (fact > 0) { res += fact / p; fact /= p; } return res; } int findMinPower(int fact, int n) { int res = INT_MAX; for (int i = 2; i <= sqrt(n); i++) { int cnt = 0; if (n % i == 0) { cnt++; n = n / i; } if (cnt > 0) { int curr = getPowerPrime(fact, i) / cnt; res = min(res, curr); } } if (n >= 2) { int curr = getPowerPrime(fact, n); res = min(res, curr); } return res; } int main() { int fact = 146, n = 5; cout << "Minimum power: " << findMinPower(fact, n); }
출력
Minimum power: 35