結果

問題 No.2074 Product is Square ?
ユーザー 👑 KazunKazun
提出日時 2022-09-16 22:48:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,905 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 92,516 KB
最終ジャッジ日時 2024-06-01 13:47:41
合計ジャッジ時間 26,649 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
78,868 KB
testcase_01 AC 1,972 ms
85,552 KB
testcase_02 TLE -
testcase_03 AC 1,979 ms
83,516 KB
testcase_04 AC 1,985 ms
83,764 KB
testcase_05 AC 1,994 ms
83,164 KB
testcase_06 AC 1,979 ms
82,936 KB
testcase_07 AC 1,970 ms
83,256 KB
testcase_08 AC 1,984 ms
83,384 KB
testcase_09 AC 1,987 ms
83,800 KB
testcase_10 AC 1,972 ms
83,200 KB
testcase_11 TLE -
testcase_12 TLE -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def Prime_List(N):
    """ N 以下の素数を列挙

    [Input]
    N: 自然数

    [Output]
    N 以下の素数を昇順に並べたリスト [2,3,5,...]
    """

    if N==0 or N==1:
        return []
    elif N==2:
        return [2]

    if N%2==0:
        N-=1

    M=(N+1)//2

    prime=[1]*M # prime[k]:=2k+1 は素数?

    for x in range(4,M,3):
        prime[x]=0

    a=5
    Flag=0
    while a*a<=N:
        if prime[(a-1)>>1]:
            ii=(a*a-1)>>1
            for j in range(ii,M,a):
                prime[j]=0
        a+=2+2*Flag
        Flag^=1

    X=[(k<<1)|1 for k in range(M) if prime[k]]
    X[0]=2

    return X

#floor(a^(1/k)) を求める.
def Floor_Root(a,k):
    """floor(a^(1/k)) を求める.

    a:非負整数
    k:正の整数
    """
    assert 0<=a and 0<k
    if a==0: return 0
    if k==1: return a

    #大体の値を求める.
    x=int(pow(a,1/k))

    #増やす
    while pow(x+1,k)<=a:
        x+=1

    #減らす
    while pow(x,k)>a:
        x-=1
    return x
#==================================================
from collections import defaultdict
from math import gcd,isqrt
#==================================================
def is_square(x):
    y=isqrt(x)
    return y*y==x

Primes=Prime_List(10**6)

def solve():
    N=int(input())
    A=list(map(int,input().split()))

    D=defaultdict(int)
    for i in range(N):
        for p in Primes:
            while A[i]%p==0:
                A[i]//=p
                D[p]+=1
    for p in D:
        if D[p]%2==1:
            return False

    for i in range(N):
        if is_square(A[i]):
            A[i]=1

    for i in range(N):
        for j in range(i+1,N):
            g=gcd(A[i], A[j])
            A[i]//=g
            A[j]//=g

    return all([a==1 for a in A])

#==================================================
T=int(input())
for _ in range(T):
    print("Yes" if solve() else "No")
0