結果
問題 |
No.2075 GCD Subsequence
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:25:00 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,604 bytes |
コンパイル時間 | 505 ms |
コンパイル使用メモリ | 82,096 KB |
実行使用メモリ | 139,432 KB |
最終ジャッジ日時 | 2025-06-12 13:31:11 |
合計ジャッジ時間 | 38,137 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 TLE * 1 -- * 12 |
ソースコード
MOD = 998244353 def main(): import sys input = sys.stdin.read().split() N = int(input[0]) A = list(map(int, input[1:N+1])) 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 from collections import defaultdict sum_d = defaultdict(int) answer = 0 for x in A: if x == 1: primes = [] else: primes = set() tmp = x while tmp != 1: p = spf[tmp] primes.add(p) while tmp % p == 0: tmp //= p primes = sorted(primes) if not primes: dp_i = 1 answer = (answer + dp_i) % MOD continue n = len(primes) total = 0 for mask in range(1, 1 << n): bits = bin(mask).count('1') d = 1 for i in range(n): if mask & (1 << i): d *= primes[i] sign = (-1) ** (bits + 1) total = (total + sign * sum_d.get(d, 0)) % MOD dp_i = (1 + total) % MOD answer = (answer + dp_i) % MOD for mask in range(1, 1 << n): d = 1 for i in range(n): if mask & (1 << i): d *= primes[i] sum_d[d] = (sum_d[d] + dp_i) % MOD print(answer % MOD) if __name__ == '__main__': main()