結果

問題 No.2074 Product is Square ?
ユーザー faculty_of_900faculty_of_900
提出日時 2023-01-10 23:09:48
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 12,457 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 13,824 KB
実行使用メモリ 20,124 KB
最終ジャッジ日時 2024-06-01 08:03:17
合計ジャッジ時間 8,183 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
20,124 KB
testcase_01 AC 95 ms
13,056 KB
testcase_02 AC 95 ms
13,184 KB
testcase_03 AC 99 ms
12,928 KB
testcase_04 AC 97 ms
13,056 KB
testcase_05 AC 98 ms
12,916 KB
testcase_06 AC 95 ms
13,056 KB
testcase_07 AC 97 ms
12,928 KB
testcase_08 AC 96 ms
13,056 KB
testcase_09 AC 93 ms
12,928 KB
testcase_10 AC 94 ms
13,056 KB
testcase_11 AC 1,423 ms
13,184 KB
testcase_12 AC 1,798 ms
13,056 KB
testcase_13 TLE -
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 #

# ライブラリインポート------------------------------------------
import math
import collections
#import statistics
from copy import deepcopy
from collections import defaultdict,deque
from sys import exit,setrecursionlimit
from heapq import heapify,heappush,heappop
from bisect import bisect_left,bisect_right,insort
from itertools import product,permutations,combinations,accumulate,combinations_with_replacement
from decimal import Decimal
#from numpy import array,matrix,dot,T
from functools import lru_cache
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
from string import ascii_uppercase, ascii_lowercase

# お決まり------------------------------------------------
INF=10**18  # まれに足りない場合もある
MOD=10**9+7
mod=998244353
def YesNo(b): print("Yes") if b else print("No")
def YESNO(b): print("YES") if b else print("NO")
dxy4=[(1,0),(-1,0),(0,1),(0,-1)]
dxy8=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
ALPHA=ascii_uppercase
alpha=ascii_lowercase
setrecursionlimit(2*10**5)
def PrintHW(array,hight,width):
    for i in range(hight): print(*array[i][:width])
def sortx(array,num): return sorted(array, key=lambda x:x[num])
def sortxr(array,num): return sorted(array, key=lambda x:x[num], reverse=True)
def LL(h,w,e=0): return [[e for i in range(w)] for j in range(h)]
def LLL(a,b,c,e=0): return [LL(b,c,e) for _ in range(a)]
def LLLL(a,b,c,d,e=0): return [LLL(b,c,d,e) for _ in range(a)]
def DD(): return defaultdict(int)  # 初期値指定ならdefaultdict(lambda: 1)などとする
def LB(n): return [[] for _ in range(n)]
def Dc(x): return Decimal(str(x))
#@lru_cache(maxsize=2*10**5)

# 入力----------------------------------------------------
def II(): return int(input())
def MI(): return map(int, input().split())
def TI(): return tuple(map(int, input().split()))
def LI(): return list(MI())
def SLI(): return sorted(LI())
def MS(): return map(str, input().split())
def LS(): return list(MS())
def LLI(rows): return [LI() for _ in range(rows)]
def LLS(rows): return [list(input()) for _ in range(rows)]
def Graph0(vertex,edge,LLI):
    ret=[[] for _ in range(vertex)]
    for [u,v] in LLI:
        u-=1; v-=1;  # 消す場合もあり
        ret[u].append(v); ret[v].append(u);
    return ret
def Banhei(hight,width,LLS,wall='#'):  # 01マップなら0
    ret=[[wall]*(width+2)]
    for i in range(hight):
        ret.append([wall]+LLS[i]+[wall])
    ret.append([wall]*(width+2))
    return ret
def MLI(n):  # [A,B] = MLI(N)のように使う
    arr=LLI(n); l=len(arr[0])
    ret=[[] for _ in range(l)]
    for i in range(n):
        for j in range(l): ret[j].append(arr[i][j])
    return ret
def ALLI():  # 何個与えられるかわからないとき
    res=[]
    while True:
        try: res.append(LI())
        except: break
    return res

# 出力カンペ--------------------------------------------
"""
print(''.join(['a', 'b', 'c'])) # abc
print("{:b}".format(b)) # 1100101010  2進数表記 
print("{:o}".format(b)) # 1452        8進数表記
print("{:x}".format(b)) # 32a         16進数小文字表記
print("{:X}".format(b)) # 32A         16進数大文字表記
print("python".ljust(15,'-')) # 左詰め python---------
print("python".center(15,'-'))# 中寄せ -----python----
print("python".rjust(15,'-')) # 右詰め ---------python
print(str(29).rjust(10,'0')) # 10桁ゼロ埋め 0000000029
print("{:.8f}".format(a/b)) # 小数点以下の桁数指定表示
N='aiueokakikukeko'
N=N.translate(str.maketrans({'a':'A'}))  #N = AiueokAkikukeko
"""

# 頻出ツール------------------------------------------
def acc(A):
    # 配列Aの累積和、最初に0を追加する。
    return [0] + list(accumulate(A))
def acc2d(A,H,W):
    # サイズH*Wの2次元配列Aの2次元累積和。先頭に0を挿入。
    B=LL(H+1,W+1)
    for x in range(H):
        for y in range(W):
            B[x+1][y+1]=A[x][y]
    for x in range(H+1):
        for y in range(1,W+1):
            B[x][y] += B[x][y-1]
    for x in range(1,H+1):
        for y in range(W+1):
            B[x][y] += B[x-1][y]
    return B
def fac(n, m=0):
    # nの階乗 | m:mod(デフォなし)
    if(n<=0): return 0
    P = 1
    for i in range(1,n+1):
        P *= i
        if(m>0): P %= m
    return P
def nCmMOD(A,B,Mod):
    # a conb b を Mod で割った余り 1絡みの挙動に注意する。
    # 大量にほしいときは階乗逆元を使うやつを持ってくる。
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod
def comb_table(N):
    # nCkのテーブルを作る, nCk = C[n][k]
    C = [[0 for i in range(N+1)] for j in range(N+1)]
    C[0][0] = 1
    for n in range(1,N+1):
        for k in range(n+1):
            C[n][k] = C[n-1][k-1] + C[n-1][k]
    return C
def nHk(A,B,Mod):
    # 重複組合せ:1~nの中から重複を許してk個のものを選ぶ組合せ
    return nCmMOD(A-1+B,A-1,Mod)
def factorization(n):
    # 素因数分解、1に注意
    arr = []; temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1: arr.append([temp, 1])
    if arr==[]: arr.append([n, 1])
    return arr
def get_primes(n: int) -> list:
    # n以下の素数表
    sieve=[1]*n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i] = [0] * ((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]
#@lru_cache(maxsize=2*10**5)
def division(a, b, m):
    # a÷bをmod mで求める 大量に使うときはメモ化
    return (a * pow(b, m - 2, m)) % m
memod=defaultdict(lambda:-1)
def gcd(a,b):
    # 最大公約数
    while b!=0: a,b = b,a%b
    return a
def lcm(a,b):
    # 最小公倍数
    return(a*b // gcd(a,b))
def make_divisors(n):
    # nの約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    #divisors.sort()
    return(divisors)
def ran(A):
    # ランレングス圧縮
    L = list(A); T = []
    for i in range(len(L)):
        if i==0: T.append([L[0],1])
        else:
            if L[i]==L[i-1]: T[-1][1]+=1
            else: T.append([L[i],1])
    #return T
    ans1,ans2=[],[]
    for i in range(len(T)):
        ans1.append(T[i][0]) #種目
        ans2.append(T[i][1]) #個数
    return ans1,ans2
def dot(P,Q,a,b,c):
    # P(a,b), Q(b,c) の行列積, abcに1が入るときは注意
    ret = LL(a,c)
    for i in range(a):
        for j in range(c):
            for k in range(b):
                ret[i][j] += P[i][k] * Q[k][j]
    return ret
def Trans(arr,h,w):
    # 配列の転置
    ret=LL(w,h)
    for i in range(h):
        for j in range(w): ret[j][i] = arr[i][j]
    return ret

# Union-Find---------------------------------------
#Root=list(range(N))
#Size=[1]*N
def find_root(root,x):
    y = root[x]
    if x == y: return x
    z = find_root(root,y)
    root[x] = z
    return z
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y: return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
def getValue(root,size,x):
    return size[find_root(root,x)]
def same(root,x,y):
    return (find_root(root,x)==find_root(root,y))

# itertools
"""
array=[1,2,3]
PMT = permutations(array) #順列
#123,132,213,231,312,321
PMT2 = permutations(array,2)
#12,13,21,23,31,32
CMB1 = combinations(array,2) #組合せ
#12,13,23
CMB2 = combinations_with_replacement(array,2) #重複組合せ
#11,12,13,22,23,33
def all_comb(array):
    #全組合せ(個数1~N)
    ret=[]
    for i in range(len(array)+1):
        ret+=list(combinations(array,i))
    return ret
#-,1,2,3,12,13,23,123
array2=[0,1]
PRD1 = product(array2,repeat=3) #直積
#000,001,010,011,100,101,110,111
"""


"""
#A
N=II()
print(5*(3+math.sqrt(5))*N**3/12)
"""

"""
#B
N=II()
A=LI()
"""

"""
def sft(x):
    return x//2 + (2**15 * (x%2))


for S in range(3):
    print(S)
    for i in range(4):
        print(S, sft(S), "{:b}".format(sft(S)))
        S=sft(S)
        
"""
"""
2**16まで、どのような変化をたどるのかを見る



"""

"""
#C
N,M=MI()
G=LB(N)
E=[]
for i in range(M):
    u,v=MI()
    u-=1
    v-=1
    u,v=min(u,v),max(u,v)
    G.append((u,i))
    G.append((v,i))
    E.append((u,v))

# 多分逆にやるUFのやつ
# 辺xがi番目の操作によって取り除かれているのかのiを探す。

Root=list(range(N))
Size=[1]*N
SCORE=[0]*N

for x in range(M)[::-1]:
    (u,v)=E[x]
    if same(Root,u,v):
        U,V=find_root(Root,u), find_root(Root,v)
        #print('a')
        new = SCORE[U] + 1
        SCORE[U] = new
        SCORE[V] = new
    else:
        #print('b')
        U,V=find_root(Root,u), find_root(Root,v)
        merge(Root, Size, u, v)
        new = max(SCORE[U], SCORE[V]) + 1
        SCORE[U] = new
        SCORE[V] = new
    #print(u,v,SCORE)

print(max(SCORE))



"""





"""
#D
N=II()
S=input()

# 0番目スタートで固める場合、1,2の3通りを試す

c=[0,0,0]
o=[0,0,0]
n=[0,0,0]
for i in range(3*N):
    if S[i]=='c':
        #print('c', i)
        c[i%3]+=1
    elif S[i]=='o':
        #print('o', i)
        o[i%3]+=1
    elif S[i]=='n':
        #print('n', i)
        n[i%3]+=1

A0 = min([c[0],o[1],n[2]])
A1 = min([c[1],o[2],n[0]])
A2 = min([c[2],o[0],n[1]])
ANS = sum([A0,A1,A2])
#print(ANS)

#print(c,o,n)

if ANS==N:
    if S=='con'*N:
        print(ANS)
    else:
        print(ANS-1)
else:
    print(ANS)

# onconcみたいな場合、2ではない





"""


"""

#B

N=II()
A=LI()

def sft(x):
    return x//2 + (2**15 * (x%2))
/*
実験
S=5
print()
for i in range(20):
    #print(S, sft(S))
    print(str("{:b}".format(sft(S))).rjust(16,'0'))
    S=sft(S)
*/

# shift(x)は周期的。0はどれだけやっても変わらない。
# 各周期を出して、そこから上から各桁について最終的な答えを1にできるかを試す?
# 16桁の2進数で表したときに、好きな位置スタートでその数を置いたようなものになる。
# つまり、1以上の数が16個以上あれば、必ず答えはMAXになる。
# それ以下の場合、もちろん全探索はできないが



if len(A)>=16:
    print(65535)
else:

    S=LB(N)
    for i in range(N):
        for j in range(20):
            if j==0:
                S[i].append(A[i])
            else:
                S[i].append(sft(S[i][-1]))
    #print(S)

    dp=LL(N+1, 65536, False)
    # dp[x][y] := x番目まで使って答えをちょうどyにすることはできるか
    dp[0][0] = True
    for i in range(N):
        for j in range(65536):
            if dp[i][j]:
                for k in S[i]:
                    dp[i+1][j | k] = True
    
    ANS=0
    for i in range(65536):
        if dp[N][i]: ANS=max(ANS,i)
    print(ANS)



"""




"""
#E

# 普通に考えるのは、Aiをすべて素因数分解して
# その素因数の登場回数の合計が全部偶数になっているかどうかを見る

# 当然TLE
T=II()


for t in range(T):

    N=II()
    A=LI()
    D=DD()

    for a in A:
        F = factorization(a)
        for [b,c] in F:
            D[b] += c

    ANS=True

    for i in D.keys():
        if D[i]%2: ANS=False

    YesNo(ANS)
"""

#E-2
T=II()

# その素因数が2個以上あるとは、1個の要素がその素因数を2個以上もっている場合か、
# その素因数をgcdとしてくくりだして捨てられる場合がある。
# くくりだして捨てることをすべての要素ペアについて行い、その後のAは各要素が平方数である場合にしかYesにならない。


def isSquare(x):
    l,r=0,10**10
    m=(l+r)//2
    while r-l>1:
        if m*m==x:
            return True
        elif m*m>x:
            r=m
        else:
            l=m
        m=(l+r)//2
    return False



for t in range(T):

    N=II()
    A=LI()
    
    for i in range(N):
        for j in range(N):
            if i==j: continue
            GCD = gcd(A[i], A[j])
            A[i] //= GCD
            A[j] //= GCD

    flag=True
    for i in A:
        flag = flag and isSquare(i)
    YesNo(flag)










"""




#F

N=II()
A=LI()




"""





0