C++ में अज्ञात संख्याओं के दिए गए उत्पाद से अधिकतम GCD

मान लीजिए हमारे पास दो पूर्णांक N और P हैं। P, N अज्ञात पूर्णांकों का उत्पाद है। हमें उन पूर्णांकों का GCD ढूंढना है। ऐसे पूर्णांकों के अलग-अलग समूह संभव हैं जो समान परिणाम देंगे। यहां हम सभी संभावित समूहों में से अधिकतम 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 है।

तकनीक ऐसी है, मान लीजिए g, a₁, a₂, … a_n का GCD है। तब ai, g का गुणक है, और P, (a₁ * a₂ * … * a_n) होना चाहिए gⁿ का गुणक। उत्तर अधिकतम g है जैसे कि gⁿ mod P = 0। अब मान लीजिए P = k1^p1 * k2^p1 * … * kn^pn। g का रूप ऐसा होना चाहिए, फिर g को अधिकतम करने के लिए, हमें p_i = p_i / N चुनना होगा।

उदाहरण

#include <iostream> #include <cmath> using namespace std; long getMaxGCD(long n, long p) {    int count = 0;    long gcd = 1;    while (p % 2 == 0) {       p >>= 1;       count++; //P के 2 से विभाजित होने की संख्या    }    if (count > 0) //यदि p में कुछ 2 हैं, तो       gcd = gcd * (long)pow(2, count / n);    for (long i = 3; i <= sqrt(p); i += 2) { //2 के बाद सभी संख्याओं की जांच       count = 0;       while (p % i == 0) {          count++;          p = p / i;       }       if (count > 0) {          gcd = gcd * (long)pow(i, count / n);       }    }    // यदि अंत में n एक अभाज्य संख्या है    if (p > 2)       gcd = gcd * (long)pow(p, 1 / n);    return gcd; } int main() {    long n = 3;    long p = 24;    cout << "MAX GCD: " << getMaxGCD(n, p); }

आउटपुट

MAX GCD: 2