結果

問題 No.719 Coprime
ユーザー lam6er
提出日時 2025-03-20 20:52:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,731 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 82,848 KB
最終ジャッジ日時 2025-03-20 20:52:27
合計ジャッジ時間 10,135 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 56 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])

    # Sieve of Eratosthenes to get the smallest prime factors
    spf = [0] * (N + 1)
    for i in range(2, N + 1):
        if spf[i] == 0:
            spf[i] = i
            for j in range(i * i, N + 1, i):
                if spf[j] == 0:
                    spf[j] = i

    # Get list of primes
    primes = [i for i in range(2, N + 1) if spf[i] == i]

    # Compute maximum prime powers for each prime
    max_power = {}
    for p in primes:
        e = 1
        while p ** (e + 1) <= N:
            e += 1
        max_power[p] = p ** e

    # Compute S, the sum of max prime powers
    S = sum(max_power.values())

    # Generate candidates (d, mask) where d is the gain and mask is a bitmask of primes
    candidates = []
    # Create a list to map primes to indices for bitmask
    prime_to_index = {p: i for i, p in enumerate(primes)}
    # Precompute factors for each number
    for n in range(2, N + 1):
        # Factorize n into its distinct primes
        factors = []
        temp = n
        seen_primes = set()
        while temp > 1:
            p = spf[temp]
            if p not in seen_primes:
                seen_primes.add(p)
                factors.append(p)
            while temp % p == 0:
                temp //= p
        if len(factors) < 2:
            continue  # Skip numbers with less than 2 distinct primes
        sum_max = sum(max_power[p] for p in factors)
        d = n - sum_max
        if d > 0:
            mask = 0
            for p in factors:
                mask |= 1 << prime_to_index[p]
            candidates.append((d, mask))

    # Sort candidates in descending order of d to facilitate pruning
    candidates.sort(reverse=True, key=lambda x: x[0])

    # Precompute suffix sums for pruning
    suffix_sums = [0] * (len(candidates) + 1)
    for i in range(len(candidates)-1, -1, -1):
        suffix_sums[i] = candidates[i][0] + suffix_sums[i+1]

    max_gain = 0

    def backtrack(index, current_gain, current_mask):
        nonlocal max_gain
        if current_gain + suffix_sums[index] <= max_gain:
            return
        if index >= len(candidates):
            if current_gain > max_gain:
                max_gain = current_gain
            return
        # Skip current candidate
        backtrack(index + 1, current_gain, current_mask)
        # Include current candidate if possible
        d, mask = candidates[index]
        if (current_mask & mask) == 0:
            new_mask = current_mask | mask
            backtrack(index + 1, current_gain + d, new_mask)

    if len(candidates) > 0:
        backtrack(0, 0, 0)

    print(S + max_gain)

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