結果
問題 | No.2074 Product is Square ? |
ユーザー | taiga0629kyopro |
提出日時 | 2022-09-16 22:06:59 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,576 bytes |
コンパイル時間 | 1,301 ms |
コンパイル使用メモリ | 86,780 KB |
実行使用メモリ | 84,444 KB |
最終ジャッジ日時 | 2023-08-23 15:41:59 |
合計ジャッジ時間 | 31,709 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 109 ms
74,508 KB |
testcase_01 | AC | 746 ms
83,584 KB |
testcase_02 | AC | 731 ms
83,224 KB |
testcase_03 | AC | 733 ms
83,264 KB |
testcase_04 | AC | 754 ms
83,892 KB |
testcase_05 | AC | 714 ms
83,472 KB |
testcase_06 | AC | 740 ms
83,608 KB |
testcase_07 | AC | 749 ms
82,908 KB |
testcase_08 | AC | 731 ms
83,780 KB |
testcase_09 | AC | 715 ms
82,828 KB |
testcase_10 | AC | 720 ms
83,172 KB |
testcase_11 | AC | 362 ms
83,744 KB |
testcase_12 | AC | 751 ms
83,604 KB |
testcase_13 | TLE | - |
testcase_14 | AC | 525 ms
83,684 KB |
testcase_15 | AC | 348 ms
82,404 KB |
testcase_16 | AC | 797 ms
84,276 KB |
testcase_17 | TLE | - |
testcase_18 | AC | 551 ms
83,796 KB |
testcase_19 | AC | 347 ms
82,748 KB |
testcase_20 | AC | 773 ms
83,984 KB |
testcase_21 | TLE | - |
testcase_22 | AC | 498 ms
83,552 KB |
testcase_23 | AC | 344 ms
82,720 KB |
testcase_24 | AC | 790 ms
84,140 KB |
testcase_25 | TLE | - |
testcase_26 | AC | 536 ms
83,404 KB |
testcase_27 | AC | 347 ms
82,996 KB |
testcase_28 | AC | 830 ms
84,444 KB |
testcase_29 | TLE | - |
testcase_30 | AC | 493 ms
83,176 KB |
testcase_31 | AC | 188 ms
80,764 KB |
testcase_32 | AC | 110 ms
74,368 KB |
testcase_33 | AC | 154 ms
81,276 KB |
ソースコード
# https://old.yosupo.jp/submission/90839 from random import randrange def gcd(a, b): while a: a, b = b%a, a return b def is_prime(n): if n == 2: return 1 if n == 1 or n%2 == 0: return 0 m = n - 1 lsb = m & -m s = lsb.bit_length()-1 d = m // lsb if n < 4759123141: test_numbers = [2, 7, 61] elif n < 341550071728321: test_numbers = [2, 3, 5, 7, 11, 13, 17] elif n < 3825123056546413051: test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23] else: test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for a in test_numbers: if a == n: continue x = pow(a,d,n) r = 0 if x == 1: continue while x != m: x = pow(x,2,n) r += 1 if x == 1 or r == s: return 0 return 1 def find_prime_factor(n): m = max(1,int(n**0.125)) while True: c = randrange(n) y = k = 0 g = q = r = 1 while g == 1: x = y mr = 3*r//4 while k < mr: y = (pow(y,2,n)+c)%n k += 1 while k < r and g == 1: ys = y for _ in range(min(m, r-k)): y = (pow(y,2,n)+c)%n q = q*abs(x-y)%n g = gcd(q,n) k += m k = r r <<= 1 if g == n: g = 1 y = ys while g == 1: y = (pow(y,2,n)+c)%n g = gcd(abs(x-y),n) if g == n: continue if is_prime(g): return g elif is_prime(n//g): return n//g else: return find_prime_factor(g) def factorize(n): res = {} for p in range(2,1000): if p*p > n: break if n%p: continue s = 0 while n%p == 0: n //= p s += 1 res[p] = s while not is_prime(n) and n > 1: p = find_prime_factor(n) s = 0 while n%p == 0: n //= p s += 1 res[p] = s if n > 1: res[n] = 1 return res T=int(input()) from collections import defaultdict for iii in range(T): n=int(input()) a=list(map(int,input().split())) ans=defaultdict(int) for x in a: pri=factorize(x) for p in pri:ans[p]+=pri[p] flag=1 for p in ans: if ans[p]%2==1:flag=0 print("Yes" if flag else "No")