結果
問題 | No.1665 quotient replace |
ユーザー |
|
提出日時 | 2021-09-03 21:59:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 993 ms / 3,000 ms |
コード長 | 1,615 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 273,052 KB |
最終ジャッジ日時 | 2024-12-15 13:15:42 |
合計ジャッジ時間 | 22,854 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
from collections import defaultdict class Eratosthenes(): def __init__(self, size): self.size = size self.isprime = [True] * size self.minfactor = [-1] * size self.mobius = [1] * size self.isprime[1] = False self.minfactor[1] = 1 self.eratosthenes() # 初めに篩にかけて,minfactorとisprimeを生成 def eratosthenes(self): for p in range(2, self.size): if not self.isprime[p]: continue self.minfactor[p] = p self.mobius[p] = -1 for q in range(p+p, self.size, p): self.isprime[q] = False if self.minfactor[q] == -1: self.minfactor[q] = p if (q//p) % p == 0: self.mobius[q] = 0 else: self.mobius[q] = -self.mobius[q] # 高速素因数分解 def prime_factorize(self, number): assert 1 <= number <= self.size factors = defaultdict(int) cnt = 0 while number != 1: factors[self.minfactor[number]] += 1 cnt += 1 number //= self.minfactor[number] return factors, cnt # 高速約数列挙 def divisors(self, number): res = [1] factors, cnt = self.prime_factorize(number) return cnt N = int(input()) A = list(map(int, input().split())) Nim = [0] * N era = Eratosthenes(10**6+1000) for i in range(N): a = A[i] Nim[i] = era.divisors(a) mex = 0 for n in Nim: mex ^= n if mex: print("white") else: print("black")