結果

問題 No.781 円周上の格子点の数え上げ
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:01:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,269 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 81,584 KB
実行使用メモリ 189,220 KB
最終ジャッジ日時 2025-04-15 23:03:07
合計ジャッジ時間 4,952 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 3 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

X, Y = map(int, input().split())

def sieve(n):
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    primes = [p for p in range(2, n+1) if is_prime[p] and p % 4 == 1]
    return primes

primes = sieve(Y)
primes.sort(reverse=True)  # Process larger primes first to minimize combinations early

max_contribution = 0
stack = [(0, 1, 1)]

while stack:
    idx, product, cont = stack.pop()
    if product > Y:
        continue
    if product >= X:
        current_f = 4 * cont
        if current_f > max_contribution:
            max_contribution = current_f
    if idx >= len(primes):
        continue
    p = primes[idx]
    max_e = 0
    current_p_power = 1
    powers = [1]
    while product * current_p_power * p <= Y:
        current_p_power *= p
        powers.append(current_p_power)
        max_e += 1
    # Iterate exponents from max_e down to 0 to process larger exponents first
    for e in range(max_e, -1, -1):
        new_product = product * powers[e]
        new_cont = cont * (e + 1)
        stack.append((idx + 1, new_product, new_cont))

print(max_contribution)
0