問題

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_a

$N$ 個の $1$ 以上の整数 $a_1, a_2, \cdots, a_N$ がある。 $a_1 \times a_2 \times \cdots \times a_N = P$ であるとき、 $max(gcd(a_1, a_2, \cdots, a_N))$ を求めよ。

制約

$1 \le N \le 10^{12}$
$1 \le P \le 10^{12}$

考え方

こういうのは $g = gcd(a_1, a_2, \cdots, a_N))$ として考えるとよい。 $a_i = a_i' \times g$ となるので与式は $g^n \times (a_1' \times a_2' \times \cdots \times a_N') = P$ となる。

また $P$ を素因数分解して $P = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$ と表せたとする。するとそれぞれの素因数の数 $e_1, e_2, \cdots, e_k$ を $N$ つの $a_i$ にそれぞれ分配することで最大値を達成できることがわかる。よって最大公約数 $g$ は以下となる。

$\displaystyle g = p_1^{\lfloor \frac{e_1}{N} \rfloor} \times p_2^{\lfloor \frac{e_2}{N} \rfloor} \times \cdots \times p_k^{\lfloor \frac{e_k}{N} \rfloor}$