結果

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

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict

def main():
    MOD = 998244353
    MAX_A = 10**6
    spf = list(range(MAX_A + 1))  # Initialize spf[i] = i

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

    N = int(stdin.readline())
    A = list(map(int, stdin.readline().split()))

    dp = defaultdict(int)
    total = 0

    for num in A:
        if num == 1:
            primes = set()
        else:
            x = num
            primes = set()
            while x != 1:
                p = spf[x]
                primes.add(p)
                while x % p == 0:
                    x //= p

        sum_val = 0
        for p in primes:
            sum_val += dp[p]
            if sum_val >= MOD:
                sum_val -= MOD
        sum_val %= MOD
        new_count = (sum_val + 1) % MOD

        for p in primes:
            dp[p] = (dp[p] + new_count) % MOD

        total = (total + new_count) % MOD

    print(total % MOD)

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