結果

問題 No.719 Coprime
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:00:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,061 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 66,388 KB
最終ジャッジ日時 2025-06-12 19:00:25
合計ジャッジ時間 4,456 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 44 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    N = int(input().strip())
    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(math.sqrt(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]

    # Compute max_prime_power for each prime
    max_prime_power = {}
    for p in primes:
        max_pow = p
        while max_pow * p <= N:
            max_pow *= p
        max_prime_power[p] = max_pow

    # Generate composite numbers (non-primes >= 2)
    composites = []
    for num in range(2, N + 1):
        if not sieve[num]:
            composites.append(num)
    composites.sort(reverse=True)

    # Track which primes are invalidated (their max_prime_power is not used)
    valid_primes = set(max_prime_power.keys())
    total = sum(max_prime_power[p] for p in valid_primes)

    # Process each composite number in descending order
    for x in composites:
        # Factorize x to get its unique prime factors
        factors = set()
        temp = x
        for p in primes:
            if p * p > temp:
                break
            if temp % p == 0:
                factors.add(p)
                while temp % p == 0:
                    temp //= p
        if temp > 1:
            factors.add(temp)
        # Check if all factors are primes (handle case where temp is a prime)
        valid = True
        sum_powers = 0
        for p in factors:
            if p not in valid_primes or p not in max_prime_power:
                valid = False
                break
            sum_powers += max_prime_power[p]
        if not valid:
            continue
        if x > sum_powers:
            total += x - sum_powers
            # Invalidate the primes in factors
            for p in factors:
                if p in valid_primes:
                    valid_primes.remove(p)

    print(total)

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