UCLN lớn nhất từ tích các số chưa biết cho trước trong C++

Cho N và P (tích của N số nguyên). Tìm UCLN lớn nhất có thể của N số đó. (Bài toán trùng với ID 1003081890 nhưng triển khai khác).

Ý tưởng: UCLN g của các số a1..an => mỗi ai là bội của g => P chia hết cho g^N. Tìm g lớn nhất sao cho g^N | P. Phân tích thừa số nguyên tố P = ∏ p_i^k_i. Thì g = ∏ p_i^(k_i / N) (lấy phần nguyên).

Ví dụ minh họa

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

long getMaxGCD(long n, long p) {
    long gcd = 1;
    // Phân tích thừa số 2
    int count = 0;
    while (p % 2 == 0) {
        p >>= 1; count++;
    }
    if (count > 0) gcd *= pow(2, count / n);
    // Phân tích các thừa số lẻ
    for (long i = 3; i <= sqrt(p); i += 2) {
        count = 0;
        while (p % i == 0) {
            count++; p /= i;
        }
        if (count > 0) gcd *= pow(i, count / n);
    }
    // Nếu p còn lại là số nguyên tố > 2
    if (p > 2) gcd *= pow(p, 1 / n); // 1/n = 0 nếu n>1, nên không ảnh hưởng
    return gcd;
}

int main() {
    long n = 3, p = 24;
    cout << "MAX UCLN: " << getMaxGCD(n, p);
    return 0;
}

Kết quả

MAX UCLN: 2