結果
問題 |
No.2075 GCD Subsequence
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:30:21 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,230 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 113,664 KB |
最終ジャッジ日時 | 2025-06-12 15:30:29 |
合計ジャッジ時間 | 8,525 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 2 WA * 26 |
ソースコード
import sys from collections import defaultdict def main(): MOD = 998244353 max_a = 10**6 # Precompute smallest prime factors 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 N = int(sys.stdin.readline()) A = list(map(int, sys.stdin.readline().split())) dp = defaultdict(int) answer = 0 for a in A: if a == 1: answer = (answer + 1) % MOD continue # Factorize a into unique primes factors = set() x = a while x != 1: p = spf[x] factors.add(p) while x % p == 0: x = x // p if not factors: answer = (answer + 1) % MOD continue sum_dp = 0 for p in factors: sum_dp = (sum_dp + dp[p]) % MOD total = (sum_dp + 1) % MOD for p in factors: dp[p] = (dp[p] + total) % MOD answer = (answer + total) % MOD print(answer % MOD) if __name__ == "__main__": main()