Power sequence

2 secs 1024 MB

この問題は与えられた数列 $A$ の全ての要素 $A_i$ に対して、 $2$ 以上の数で割り切れる最初の整数 $x$ を探索し、 $A_i$ が $x$ の累乗であるかを判定することで解くことができます。 $A_i$ が $x$ の累乗であるかどうかは $A_i$ を $x$ で割り続けた結果が $1$ であるか判定することで調べることができます。

以下は Python の実装例です。

xxxxxxxxxx
 
n = int(input())
a = list(map(int, input().split()))
ok = True  # 全ての要素が累乗であるか
for i in range(n):
    flag = False  # 要素A_iが累乗であるか
    for j in range(2, 10**3 + 1):
        if a[i] % j == 0:
            while a[i] % j == 0:
                a[i] //= j
            if a[i] == 1:
                flag = True
            break
    if not flag:
        ok = False
        break
print("Yes" if ok else "No")