結果
問題 |
No.1746 Sqrt Integer Segments
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:22:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 540 ms / 2,000 ms |
コード長 | 1,483 bytes |
コンパイル時間 | 226 ms |
コンパイル使用メモリ | 81,928 KB |
実行使用メモリ | 146,156 KB |
最終ジャッジ日時 | 2025-03-20 20:24:29 |
合計ジャッジ時間 | 11,777 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
import sys import random from collections import defaultdict def main(): input = sys.stdin.read().split() n = int(input[0]) a = list(map(int, input[1:n+1])) max_prime = 10**6 spf = list(range(max_prime + 1)) for i in range(2, int(max_prime**0.5) + 1): if spf[i] == i: for j in range(i*i, max_prime+1, i): if spf[j] == j: spf[j] = i # Generate primes and their hash values primes = set() for i in range(2, max_prime + 1): if spf[i] == i: primes.add(i) # Assign random 64-bit hashes to primes prime_hash = {} for p in primes: prime_hash[p] = random.getrandbits(64) current_hash = 0 counter = defaultdict(int) counter[current_hash] = 1 answer = 0 for num in a: temp = num delta = set() while temp > 1: p = spf[temp] cnt = 0 while temp % p == 0: cnt += 1 temp = temp // p if cnt % 2 == 1: if p in delta: delta.remove(p) else: delta.add(p) # Compute delta_hash delta_hash = 0 for p in delta: delta_hash ^= prime_hash[p] current_hash ^= delta_hash answer += counter.get(current_hash, 0) counter[current_hash] += 1 print(answer) if __name__ == "__main__": main()