結果
問題 |
No.2075 GCD Subsequence
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:40:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,019 ms / 4,000 ms |
コード長 | 1,804 bytes |
コンパイル時間 | 520 ms |
コンパイル使用メモリ | 82,072 KB |
実行使用メモリ | 133,968 KB |
最終ジャッジ日時 | 2025-06-12 20:40:47 |
合計ジャッジ時間 | 26,898 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
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()