UCLN lớn nhất của N số nguyên với tích cho trước trong C++

Cho hai số nguyên N và P. P là tích của N số nguyên chưa biết. Tìm UCLN lớn nhất có thể của N số đó. Ví dụ: N=3, P=24. Các nhóm có thể: {1,1,24}, {1,2,12}, {1,3,8}, {1,4,6}, {2,2,6}, {2,3,4}. UCLN tương ứng: 1,1,1,1,2,1. Đáp án là 2.

Phân tích thừa số nguyên tố của P. UCLN lớn nhất khi các thừa số nguyên tố phân bố đều cho N số. Công thức: UCLN = ∏ p_i^(k_i / N) (lấy phần nguyên).

Ví dụ minh họa

#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;

long getMaxGCD(long N, long p) {
    long 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 UCLN: " << getMaxGCD(n, p);
    return 0;
}

Kết quả

MAX UCLN: 2