結果

問題 No.719 Coprime
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:40:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,141 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 60,060 KB
最終ジャッジ日時 2025-06-12 16:40:39
合計ジャッジ時間 3,769 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().strip()
    N = int(input)

    if N < 2:
        print(0)
        return

    # Sieve of Eratosthenes to find primes up to N
    sieve = [True] * (N + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i]:
            sieve[i*i : N+1 : i] = [False] * len(sieve[i*i : N+1 : i])
    
    primes = [p for p in range(2, N + 1) if sieve[p]]

    # Compute largest prime power for each prime
    x = {}
    for p in primes:
        current = p
        while current * p <= N:
            current *= p
        x[p] = current

    initial_sum = sum(x[p] for p in primes)
    max_gain = 0

    # Iterate through all pairs of primes p < q
    for i in range(len(primes)):
        p = primes[i]
        for j in range(i + 1, len(primes)):
            q = primes[j]
            product = p * q
            if product > N:
                continue
            gain = product - (x[p] + x[q])
            if gain > max_gain:
                max_gain = gain

    final_sum = initial_sum + max_gain
    print(final_sum)

if __name__ == "__main__":
    main()
0