結果

問題 No.719 Coprime
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:04:13
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,629 bytes
コンパイル時間 600 ms
コンパイル使用メモリ 82,008 KB
実行使用メモリ 695,876 KB
最終ジャッジ日時 2025-04-16 00:05:52
合計ジャッジ時間 8,139 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43 MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline().strip())
    if N == 2:
        print(2)
        return

    # Sieve of Eratosthenes to find smallest prime factors
    spf = list(range(N + 1))
    for i in range(2, int(math.sqrt(N)) + 1):
        if spf[i] == i:
            for j in range(i*i, N+1, i):
                if spf[j] == j:
                    spf[j] = i

    # Function to get prime factors
    def get_factors(x):
        factors = set()
        while x > 1:
            p = spf[x]
            factors.add(p)
            while x % p == 0:
                x //= p
        return factors

    # Collect all primes up to N
    primes = []
    for x in range(2, N+1):
        if spf[x] == x:
            primes.append(x)
    prime_index = {p:i for i, p in enumerate(primes)}

    numbers = list(range(2, N+1))
    numbers.sort(reverse=True)

    dp = {}
    dp[0] = 0  # 0 used primes, sum 0

    for x in numbers:
        factors = get_factors(x)
        if not factors:
            continue
        mask = 0
        for p in factors:
            if p not in prime_index:
                mask = -1
                break
            mask |= 1 << prime_index[p]
        if mask == -1:
            continue
        items = list(dp.items())
        for curr_mask, curr_sum in items:
            if (curr_mask & mask) == 0:
                new_mask = curr_mask | mask
                new_sum = curr_sum + x
                if new_sum > dp.get(new_mask, 0):
                    dp[new_mask] = new_sum

    print(max(dp.values()))

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