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

আমরা P-এর সব প্রাইম ফ্যাক্টর বের করে হ্যাশম্যাপে রাখব। N পূর্ণসংখ্যাগুলোর সর্বোচ্চ GCD তখন হবে যখন প্রাইম ফ্যাক্টর সব পূর্ণসংখ্যাতেই কমন থাকবে। তাই যদি P = p₁^k1 * p₂^k2 * ... * p_n^kn। এখানে pi হল প্রাইম ফ্যাক্টর। তবে সর্বোচ্চ GCD হবে res = p₁^k1/N * p₂^k2/N * ... * p_n^kn/N।

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

#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);
    return 0;
}

আউটপুট

MAX GCD: 2