結果
問題 | No.2074 Product is Square ? |
ユーザー |
![]() |
提出日時 | 2022-09-16 23:18:59 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,393 bytes |
コンパイル時間 | 489 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 79,940 KB |
最終ジャッジ日時 | 2024-12-21 22:57:04 |
合計ジャッジ時間 | 30,118 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 WA * 1 RE * 2 TLE * 5 |
ソースコード
import sys#input = sys.stdin.readline#input = sys.stdin.buffer.readline #文字列はダメ#sys.setrecursionlimit(1000000)import math#import bisect#import itertools#import random#from heapq import heapify, heappop, heappushfrom collections import defaultdict#from collections import deque#import copy #DeepCopy: hoge = [_[:] for _ in hogehoge]#from functools import lru_cache#@lru_cache(maxsize=None)#MOD = pow(10,9) + 7#MOD = 998244353#dx = [1,0,-1,0]#dy = [0,1,0,-1]#dx8 = [1,1,0,-1,-1,-1,0,1]#dy8 = [0,1,1,1,0,-1,-1,-1]def gcd(a, b):while b:a, b = b, a % breturn adef isPrimeMR(n):d = n - 1d = d // (d & -d)L = [2]for a in L:t = dy = pow(a, t, n)if y == 1:continuewhile y != n - 1:y = (y * y) % nif y == 1 or t == n - 1:return 0t <<= 1return 1#無断使用すいませんdef findFactorRho(n):m = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1while g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mr <<= 1if g == n:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), n)if g < n:if isPrimeMR(g):return gelif isPrimeMR(n // g):return n // greturn findFactorRho(g)def primeFactor(n): #これを実行i = 2ret = {}rhoFlg = 0while i * i <= n:k = 0while n % i == 0:n //= ik += 1if k:ret[i] = ki += 1 + i % 2if i == 101 and n >= 2 ** 20:while n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1:ret[n] = 1if rhoFlg:ret = {x: ret[x] for x in sorted(ret)}return ret#高速素因数分解を用いた約数全列挙import itertoolsdef factorization_fast(x):P = primeFactor(x)base = []L = []for p in P:base.append(p)temp = [i for i in range(P[p]+1)]L.append(temp)ret = []for T in itertools.product(*L):val = 1for i,t in enumerate(T):val *= pow(base[i],t)ret.append(val)ret.sort() #必要ならソートreturn retdef main():T = int(input())for _ in range(T):N = int(input())A = list(map(int,input().split()))dic = defaultdict(int)for a in A:PL = primeFactor(a)for p,num in PL.items():dic[p] ^= num%2if max(dic.values()) == 0:print('Yes')else:print('No')if __name__ == '__main__':main()