結果

問題 No.2075 GCD Subsequence
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:36:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,753 ms / 4,000 ms
コード長 1,804 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,544 KB
実行使用メモリ 133,840 KB
最終ジャッジ日時 2025-06-12 20:37:15
合計ジャッジ時間 24,263 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict

MOD = 998244353

def main():
    # Precompute smallest prime factors (SPF) up to 1e6
    max_a = 10**6
    spf = list(range(max_a + 1))
    for i in range(2, int(max_a**0.5) + 1):
        if spf[i] == i:
            for j in range(i*i, max_a + 1, i):
                if spf[j] == j:
                    spf[j] = i

    def get_distinct_primes(x):
        if x == 1:
            return []
        factors = set()
        while x != 1:
            p = spf[x]
            factors.add(p)
            while x % p == 0:
                x = x // p
        return sorted(factors)

    # Read input
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))

    sum_dp = defaultdict(int)
    ans = 0

    for a in A:
        if a == 1:
            dp_i = 1
        else:
            primes = get_distinct_primes(a)
            if not primes:
                dp_i = 1
            else:
                m = len(primes)
                subsets = []
                for mask in range(1, 1 << m):
                    product = 1
                    count = 0
                    for i in range(m):
                        if mask & (1 << i):
                            product *= primes[i]
                            count += 1
                    subsets.append((product, count))
                
                S_i = 0
                for x, k in subsets:
                    sign = (-1) ** (k + 1)
                    S_i += sign * sum_dp.get(x, 0)
                S_i %= MOD
                dp_i = (S_i + 1) % MOD

                for x, _ in subsets:
                    sum_dp[x] = (sum_dp[x] + dp_i) % MOD

        ans = (ans + dp_i) % MOD

    print(ans % MOD)

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