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। তাই উত্তর ২।

টেকনিকটি হলো: ধরুন 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 বেছে নিতে হবে।

C++ প্রোগ্রাম উদাহরণ

#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 ২ দিয়ে কতবার ভাগ হয়েছে
    }
    if (count > 0) // যদি P-তে ২ থাকে
        gcd = gcd * (long)pow(2, count / n);
    for (long i = 3; i <= sqrt(p); i += 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);
    return 0;
}

আউটপুট

MAX GCD: 2