結果

問題 No.3067 +10 Seconds Clock
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:01:22
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 850 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 70,828 KB
最終ジャッジ日時 2025-06-12 21:04:13
合計ジャッジ時間 2,706 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
import bisect
from collections import defaultdict

def sieve(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if sieve[i]:
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

primes = sieve(44721)
prime_squares = [p * p for p in primes]
prime_squares.sort()

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

freq = defaultdict(int)
total = 0

for x in a:
    low = x + 1
    high = x + 10**9

    left = bisect.bisect_left(prime_squares, low)
    right = bisect.bisect_right(prime_squares, high)

    for s in prime_squares[left:right]:
        y = s - x
        total += freq.get(y, 0)
    
    freq[x] += 1

print(total)
0