ধরুন আমাদের দুটি সংখ্যা n এবং fact আছে। আমাদের খুঁজে বের করতে হবে 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
