CADDi 2018 C - Product and GCD

atcoder.jp

問題概要

N個の自然数a1,a2,...aNがある。a1*a2*...*aN = P であるとき、a1,a2,...aNの最大公約数は？
1 <= N,P <= 10^12

解法

N>=Pのときは最大公約数が1になる（a1,a2,...aNは全部自然数だから、少なくとも1つは1がある）。
N = 1のときはP自身が答え。
これらでないとき、a1,a2,...aNの公約数がkとすると、P = a1*a2*...*aN はkでN回割り切れる、つまりP%(k^N)==0。
これを(k^N)がP以下の場合で順に試していくのだけど、Nは10^12以下なので、Nが大きいとTLEになる。
そこでPの制約に着目する。10^12 < 2^40より、Nが40以上ならば最大公約数は1である。
（Nが40以上だと、a1,a2,...aNが全部2だとしてもPは10^12を超えてしまうため、少なくとも1つは1。つまり最大公約数1。）

N, P = map(int,input().split())
if N >= 40 or N >= P:
    print(1)
    exit(0)
if N == 1:
    print(P)
    exit(0)

ans = 1
k = 1
while pow(k,N) <= P:
    if P%pow(k,N)==0:
        ans = k
    k += 1

print(ans)