দুইটি পূর্ণসংখ্যা n এবং k দেওয়া আছে। আমাদের x এর সর্বোচ্চ মান খুঁজে বের করতে হবে যাতে n! mod (k^x) = 0 হয়। অর্থাৎ n! কে k^x দিয়ে ভাগ করলে ভাগশেষ ০ আসে। উদাহরণস্বরূপ, n = 5 এবং k = 2 হলে আউটপুট হবে ৩। কারণ ৫! = ১২০, এবং x এর বিভিন্ন মানের জন্য:
১২০ mod 2⁰ = ০, ১২০ mod 2¹ = ০, ১২০ mod ২² = ০, ১২০ mod ২³ = ০, ১২০ mod ২⁴ = ৮, ১২০ mod ২⁵ = ২৪, ১২০ mod ২⁶ = ৫৬, ১২০ mod ২⁷ = ১২০। যেহেতু x = ৩ পর্যন্ত ভাগশেষ ০, তাই সর্বোচ্চ মান ৩।
এটি সমাধানের জন্য নিম্নলিখিত ধাপগুলো অনুসরণ করতে হবে:
- k এর বর্গমূল নেওয়া হবে এবং m-এ সংরক্ষণ করা হবে
- i := 2 থেকে m পর্যন্ত লুপ চলাতে হবে:
- যখন i = m হয়, তবে i := k সেট করা হবে
- যদি k, i দ্বারা বিভাজ্য হয়, তবে k কে i দিয়ে ভাগ করা হবে
- n পর্যন্ত লুপ চালাতে হবে এবং ভাগফল u ভেরিয়েবলে যোগ করা হবে
- প্রতিটি লুপের পর r এর ন্যূনতম মান সংরক্ষণ করা হবে
উদাহরণ
#include <iostream> #include <cmath> using namespace std; int calculateMaxX(int n, int k) { int result = n, v, u; int m = sqrt(k) + 1; for (int i = 2; i <= m && k > 1; i++) { if (i == m) { i = k; } for (u = v = 0; k % i == 0; v++) { k /= i; } if (v > 0) { int t = n; while (t > 0) { t /= i; u += t; } result = min(result, u / v); } } return result; } int main() { int n = 5; int k = 2; cout<<"Maximum value of x is: " << calculateMaxX(n, k); }আউটপুট
Maximum value of x is: 3
