मान लीजिए हमारे पास दो पूर्णांक n और k हैं। हमें x का अधिकतम मान ढूंढना है, जैसे कि n! mod (k^x) = 0। इसलिए जब n = 5, और k = 2, तो आउटपुट 3 होगा। जैसे n! = 120, अब x के विभिन्न मानों के लिए:
120 mod 2^0 = 0, 120 mod 2^1 = 0, 120 mod 2^2 = 0, 120 mod 2^3 = 0, 120 mod 2^4 = 8, 120 mod 2^5 = 24, 120 mod 2^6 = 56, 120 mod 2^7 = 120। चूंकि x का अधिकतम मान 3 है, परिणाम 0 है, इसलिए आउटपुट 3 है।
इसे हल करने के लिए, हमें इन चरणों का पालन करना होगा:
- 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
