結果
| 問題 |
No.2074 Product is Square ?
|
| コンテスト | |
| ユーザー |
 kys
|
| 提出日時 | 2022-09-16 22:20:41 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,841 bytes |
| コンパイル時間 | 156 ms |
| コンパイル使用メモリ | 82,760 KB |
| 実行使用メモリ | 161,552 KB |
| 最終ジャッジ日時 | 2024-12-21 21:35:30 |
| 合計ジャッジ時間 | 94,825 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 TLE * 31 |
ソースコード
def main():
from sys import stdin, setrecursionlimit
# setrecursionlimit(1000000)
input = stdin.readline
def iinput(): return int(input())
def sinput(): return input().rstrip()
def i0input(): return int(input()) - 1
def linput(): return list(input().split())
def liinput(): return list(map(int, input().split()))
def miinput(): return map(int, input().split())
def li0input(): return list(map(lambda x: int(x) - 1, input().split()))
def mi0input(): return map(lambda x: int(x) - 1, input().split())
INF = 1000000000000000000
MOD = 1000000007
import math
import random
class Prime:
seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def is_prime(self, n):
"""
prime test (hybrid)
see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
:param n:
:return: boolean
"""
is_prime_common = self.is_prime_common(n)
if is_prime_common is not None:
return is_prime_common
if n < 2000000:
return self.is_prime_brute_force(n)
else:
return self.is_prime_miller_rabin(n)
def is_prime_common(self, n):
if n == 1: return False
if n in Prime.seed_primes: return True
if any(map(lambda x: n % x == 0, self.seed_primes)): return False
def is_prime_brute_force(self, n):
"""
brute force prime test
use with is_prime_common if you want to skip seed_primes
:param n:
:return: boolean
"""
for k in range(2, int(math.sqrt(n)) + 1):
if n % k == 0:
return False
return True
def is_prime_miller_rabin(self, n):
"""
miller rabin prime test
use with is_prime_common if you want to skip seed_primes
see also
algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
:param n:
:return: boolean
"""
d = n - 1
while d & 1 == 0:
d >>= 1
# use one of these lines / upper is more efficient.
witnesses = self.get_witnesses(n)
# witnesses = [random.randint(1, n - 1) for _ in range(100)]
for w in witnesses:
y = pow(w, d, n)
while d != n - 1 and y != 1 and y != n - 1:
y = (y * y) % n
d <<= 1
if y != n - 1 and d & 1 == 0:
return False
return True
def get_witnesses(self, num):
def _get_range(num):
if num < 2047:
return 1
if num < 1373653:
return 2
if num < 25326001:
return 3
if num < 3215031751:
return 4
if num < 2152302898747:
return 5
if num < 3474749660383:
return 6
if num < 341550071728321:
return 7
if num < 3825123056546413051:
return 9
return 12
return self.seed_primes[:_get_range(num)]
def gcd(self, a, b):
if a < b:
return self.gcd(b, a)
if b == 0:
return a
while b:
a, b = b, a % b
return a
@staticmethod
def f(x, n, seed):
"""
pseudo prime generator
:param x:
:param n:
:param seed:
:return: pseudo prime
"""
p = Prime.seed_primes[seed % len(Prime.seed_primes)]
return (p * x + seed) % n
def find_factor(self, n, seed=1):
"""
find one of factor of n
this function is based to Pollard's rho algorithm
see also
algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98
:param n:
:param seed:
:return: factor
"""
if self.is_prime(n):
return n
x, y, d = 2, 2, 1
count = 0
while d == 1:
count += 1
x = self.f(x, n, seed)
y = self.f(self.f(y, n, seed), n, seed)
d = self.gcd(abs(x - y), n)
if d == n:
return self.find_factor(n, seed+1)
return self.find_factor(d)
def find_factors(self, n):
primes = {}
if self.is_prime(n):
primes[n] = 1
return primes
while n > 1:
factor = self.find_factor(n)
primes.setdefault(factor, 0)
primes[factor] += 1
n //= factor
return primes
prime = Prime()
for _ in [0] * iinput():
N = iinput()
A = liinput()
tmp = 0
memo = dict()
for a in A:
for k, v in prime.find_factors(a).items():
if v % 2:
if k not in memo:
memo[k] = random.randint(1, (1 << 31) - 1)
tmp ^= memo[k]
if tmp:
print('No')
else:
print('Yes')
main()