結果
問題 |
No.2075 GCD Subsequence
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:32:58 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,654 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,716 KB |
実行使用メモリ | 139,936 KB |
最終ジャッジ日時 | 2025-06-12 13:39:46 |
合計ジャッジ時間 | 16,961 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 TLE * 11 |
ソースコード
import sys import math from collections import defaultdict MOD = 998244353 def main(): max_a = 10**6 spf = list(range(max_a + 1)) for i in range(2, int(math.isqrt(max_a)) + 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())) cnt_d = defaultdict(int) total = 0 for num in a: if num == 1: total = (total + 1) % MOD continue x = num factors = set() while x > 1: p = spf[x] factors.add(p) while x % p == 0: x //= p primes = list(factors) m = len(primes) if m == 0: total = (total + 1) % MOD continue sum_contribution = 0 for mask in range(1, 1 << m): bits = bin(mask).count('1') k = bits product = 1 for j in range(m): if mask & (1 << j): product *= primes[j] sign = 1 if k % 2 == 1 else -1 term = (sign * cnt_d.get(product, 0)) % MOD sum_contribution = (sum_contribution + term) % MOD dp_i = (sum_contribution + 1) % MOD total = (total + dp_i) % MOD for mask in range(1, 1 << m): product = 1 for j in range(m): if mask & (1 << j): product *= primes[j] cnt_d[product] = (cnt_d[product] + dp_i) % MOD print(total % MOD) if __name__ == '__main__': main()