結果
問題 |
No.1746 Sqrt Integer Segments
|
ユーザー |
![]() |
提出日時 | 2022-06-12 22:22:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 904 ms / 2,000 ms |
コード長 | 1,039 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 267,256 KB |
最終ジャッジ日時 | 2024-09-24 08:35:06 |
合計ジャッジ時間 | 24,607 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
from collections import Counter U = 10 ** 6 mask = (1 << 64) - 1 def prime_sieve(N): #sieve[i] : iの最小の素因数 sieve = [0] * (N + 1) prime = [] for i in range(2, N + 1): if sieve[i] == 0: sieve[i] = i prime.append(i) for p in prime: if p > sieve[i] or i * p > N: break sieve[i * p] = p return sieve def xorshift64(seed=123456789): x = seed while 1: x = x ^ (x << 13) & mask x = x ^ (x >> 7) & mask x = x ^ (x << 17) & mask yield x def main(N, A): rnd = xorshift64() h = [next(rnd) for _ in range(U+1)] sieve = prime_sieve(U) xor = [0] * (N + 1) for i, a in enumerate(A, 1): while a > 1: p = sieve[a] xor[i] ^= h[p] a //= p xor[i] ^= xor[i-1] ans = 0 for v in Counter(xor).values(): ans += v * (v - 1) // 2 return ans N = int(input()) A = list(map(int, input().split())) print(main(N, A))