C++ में दिए गए उत्पाद के साथ N पूर्णांकों का अधिकतम GCD

मान लीजिए हमारे पास दो पूर्णांक N और P हैं। P, N अज्ञात पूर्णांकों का उत्पाद है। हमें उन पूर्णांकों के अधिकतम संभव GCD को ढूंढना है। मान लीजिए N = 3, और P = 24, तो अलग-अलग समूह होंगे जैसे {1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2, 2, 6}, {2, 3, 4}। GCD हैं: 1, 1, 1, 1, 2, 1। तो उत्तर यहां 2 है।

हम P के सभी अभाज्य गुणनखंड ढूंढेंगे, और उन्हें हैशमैप में स्टोर करेंगे। N पूर्णांकों का अधिकतम GCD तब होगा जब अभाज्य गुणनखंड सभी पूर्णांकों में सामान्य होगा। इसलिए यदि P = p₁^k1 * p₂^k2 * … * p_n^kn। यहां pi अभाज्य गुणनखंड है। तो अधिकतम GCD होगा res = p₁^k1/N * p₂^k2/N * … * p_n^kn/N।

उदाहरण

#include <iostream> #include <cmath> #include <unordered_map> using namespace std; long getMaxGCD(long N, long p) {    int gcd = 1;    unordered_map<int, int> prime_factors;    for (int i = 2; i * i <= p; i++) {       while (p % i == 0) {          prime_factors[i]++;          p /= i;       }    }    if (p != 1)       prime_factors[p]++;    for (auto v : prime_factors)       gcd = gcd * pow(v.first, v.second / N);    return gcd; } int main() {    long n = 3;    long p = 24;    cout << "MAX GCD: " << getMaxGCD(n, p); }

आउटपुट

MAX GCD: 2