結果
問題 |
No.2075 GCD Subsequence
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:39:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,600 ms / 4,000 ms |
コード長 | 1,805 bytes |
コンパイル時間 | 219 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 136,400 KB |
最終ジャッジ日時 | 2025-06-12 13:44:33 |
合計ジャッジ時間 | 33,977 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
MOD = 998244353 def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 A = list(map(int, input[idx:idx + N])) # Precompute smallest prime factors 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 factorize(x): factors = set() if x == 1: return factors while x != 1: p = spf[x] factors.add(p) while x % p == 0: x //= p return factors cnt = dict() answer = 0 for x in A: primes = factorize(x) if not primes: answer = (answer + 1) % MOD continue primes = list(primes) k = len(primes) sum_terms = 0 subsets = [] for mask in range(1, 1 << k): subset = [] for i in range(k): if mask & (1 << i): subset.append(primes[i]) subsets.append(subset) for subset in subsets: m = len(subset) d = 1 for p in subset: d *= p term = cnt.get(d, 0) if m % 2 == 1: sum_terms = (sum_terms + term) % MOD else: sum_terms = (sum_terms - term) % MOD new = (sum_terms + 1) % MOD answer = (answer + new) % MOD for subset in subsets: m = len(subset) d = 1 for p in subset: d *= p cnt[d] = (cnt.get(d, 0) + new) % MOD print(answer % MOD) if __name__ == '__main__': main()