দুটি সংখ্যা n এবং fact দেওয়া আছে। আমাদের n-এর সর্বোচ্চ ঘাত খুঁজে বের করতে হবে যা fact! (fact-এর ফ্যাক্টোরিয়াল) কে ভাগ করে দেয়। উদাহরণস্বরূপ, fact = 5 এবং n = 2 হলে আউটপুট হবে ৩। কারণ ৫! = ১২০, এবং এটি ২³ = ৮ দ্বারা বিভাজ্য।
এখানে আমরা লেজান্ড্রের সূত্র (Legendre's formula) ব্যবহার করব। এটি একটি মৌলিক সংখ্যার সর্বোচ্চ ঘাত খুঁজে বের করে যা fact! কে ভাগ করে দেয়। আমরা n-এর সব মৌলিক গুণনীয়ক খুঁজে বের করব, তারপর প্রতিটি মৌলিক গুণনীয়কের জন্য fact! কে ভাগ করে দেয় এমন সর্বোচ্চ ঘাত নির্ণয় করব।
যেমন fact = 146 এবং n = 15 হলে, n-এর মৌলিক গুণনীয়ক ৫ এবং ৩। তাই:
৩-এর জন্য: [146/3] + [48/3] + [16/3] + [5/3] + [1/3] = 48 + 16 + 5 + 1 + 0 = 70।
৫-এর জন্য: [146/5] + [29/5] + [5/5] + [1/5] = 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
