x का अधिकतम मान इस प्रकार ज्ञात कीजिए कि n! % (k^x) =0 C++ . में

मान लीजिए हमारे पास दो पूर्णांक n और k हैं। हमें x का अधिकतम मान इस प्रकार ज्ञात करना है कि n! mod (k^x) =0. तो जब n =5, और k =2, तो आउटपुट 3 होगा। जैसे n! =120, अब x के विभिन्न मानों के लिए, यह होगा -

120 मॉड 2^0 =0, 120 मॉड 2^1 =0, 120 मॉड 2^2 =0, 120 मॉड 2^3 =0, 120 मॉड 2^4 =8, 120 मॉड 2^5 =24, 120 मॉड 2^6 =56, 120 मॉड 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