結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 88 ms
80,500 KB
testcase_01 AC 1,981 ms
83,268 KB
testcase_02 TLE -
testcase_03 AC 1,974 ms
83,332 KB
testcase_04 AC 1,977 ms
83,864 KB
testcase_05 AC 1,988 ms
82,980 KB
testcase_06 AC 1,977 ms
82,300 KB
testcase_07 AC 1,977 ms
83,384 KB
testcase_08 AC 1,988 ms
82,892 KB
testcase_09 AC 1,968 ms
82,652 KB
testcase_10 AC 1,959 ms
83,376 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
#==================================================
def is_square(x):
    y=Floor_Root(x,2)
    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