結果

問題 No.2075 GCD Subsequence
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:35:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,067 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 125,184 KB
最終ジャッジ日時 2025-06-12 20:36:02
合計ジャッジ時間 10,120 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    MOD = 998244353
    MAX = 10**6
    spf = list(range(MAX + 1))  # Initialize SPF as 0 for all, then corrected.

    for i in range(2, int(MAX**0.5) + 1):
        if spf[i] == i:  # i is a prime
            for j in range(i * i, MAX + 1, i):
                if spf[j] == j:
                    spf[j] = i

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

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

    dp = defaultdict(int)
    total = 0

    for a in A:
        primes = factorize(a)
        sum_d = 0
        for p in primes:
            sum_d = (sum_d + dp[p]) % MOD
        s = (sum_d + 1) % MOD
        total = (total + s) % MOD
        for p in primes:
            dp[p] = (dp[p] + s) % MOD

    print(total % MOD)

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