結果

問題 No.719 Coprime
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:59:24
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,328 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 769,900 KB
最終ジャッジ日時 2025-06-12 18:59:41
合計ジャッジ時間 9,928 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41 MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import isqrt
from functools import lru_cache

def input():
    return sys.stdin.read()

def prime_factors(n):
    factors = set()
    while n % 2 == 0:
        factors.add(2)
        n //= 2
    i = 3
    while i <= isqrt(n):
        while n % i == 0:
            factors.add(i)
            n //= i
        i += 2
    if n > 2:
        factors.add(n)
    return factors

def main():
    N = int(input().strip())
    numbers = list(range(2, N+1))
    numbers.sort(reverse=True)
    factors_list = [prime_factors(x) for x in numbers]

    @lru_cache(maxsize=None)
    def backtrack(index, used_primes):
        if index == len(numbers):
            return 0
        current_factors = factors_list[index]
        conflict = False
        for p in current_factors:
            if (1 << p) & used_primes:
                conflict = True
                break
        if not conflict:
            new_used = used_primes
            for p in current_factors:
                new_used |= (1 << p)
            pick = numbers[index] + backtrack(index + 1, new_used)
            not_pick = backtrack(index + 1, used_primes)
            return max(pick, not_pick)
        else:
            return backtrack(index + 1, used_primes)

    max_sum = backtrack(0, 0)
    print(max_sum)

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