算法

(素因子分解) $O(\sqrt{N})$

令 $g = \gcd(a_1, a_2, \cdots, a_N)$
由 $a_1 \cdot a_2 \cdots a_N = P$ 可知 $g^N \mid P$
根据算术基本定理，$P$ 可唯一的表示为 $P = p_1^{e_1} \cdot p_2^{e_2} \cdots p_N^{e_N}$
同样 $g$ 也可以唯一地表示为 $g = p_1^{f_1} \cdot p_2^{f_2} \cdots p_N^{f_N}$
由于 $g^N$ 是 $P$ 的因子，所以必然有 $f_i \cdot N \leqslant e_i$，$f_i$ 最大可取到 $\lfloor \frac{e_i}{N}\rfloor$

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::get;
using std::pair;
using std::vector;
using ll = long long;

template<class T>
vector<pair<T, T>> PrimeFactorization(T n) {
    vector<pair<T, T>> pf;
    T m = n;
    for (T i = 2; i * i <= n; ++i) {
        if (m % i != 0) continue;
        T cnt = 0;
        while (m % i == 0) { ++cnt; m /= i; }
        pf.emplace_back(i, cnt);
    }
    if (m > 1) pf.emplace_back(m, 1);
    return pf;
}

int main() {
    ll n, p;
    cin >> n >> p;

    ll ans = 1;
    auto pf = PrimeFactorization<ll>(p);
    for (auto p : pf) {
        if (get<1>(p) >= n)
           ans *= pow(get<0>(p), get<1>(p) / n);
    }

    cout << ans << '\n';

    return 0;
}