結果

問題 No.2074 Product is Square ?
ユーザー faculty_of_900faculty_of_900
提出日時 2023-01-10 22:54:37
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 11,502 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 82,620 KB
実行使用メモリ 186,552 KB
最終ジャッジ日時 2024-12-21 12:27:18
合計ジャッジ時間 98,402 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other WA * 1 TLE * 32
権限があれば一括ダウンロードができます

ソースコード

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='#'): # 010
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):
# A0
return [0] + list(accumulate(A))
def acc2d(A,H,W):
# H*W2A20
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~nk
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÷bmod 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) , abc1
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
# xii
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()
# 01,2
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)
# onconc2
"""
"""
#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
# 162
# 116MAX
#
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
#
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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0