結果

問題 No.2074 Product is Square ?
コンテスト
ユーザー 👑 Kazun
提出日時 2022-09-16 22:46:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,906 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 170,852 KB
最終ジャッジ日時 2024-12-21 22:06:40
合計ジャッジ時間 76,423 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12 TLE * 21
権限があれば一括ダウンロードができます

ソースコード

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