結果
問題 |
No.2075 GCD Subsequence
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:28:27 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,394 bytes |
コンパイル時間 | 416 ms |
コンパイル使用メモリ | 82,476 KB |
実行使用メモリ | 141,552 KB |
最終ジャッジ日時 | 2025-06-12 15:28:51 |
合計ジャッジ時間 | 17,594 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 TLE * 1 -- * 12 |
ソースコード
import sys from collections import defaultdict def main(): MOD = 998244353 input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 A = list(map(int, input[idx:idx+N])) idx += N max_num = 10**6 spf = list(range(max_num + 1)) for i in range(2, int(max_num**0.5) + 1): if spf[i] == i: for j in range(i*i, max_num + 1, i): if spf[j] == j: spf[j] = i def get_primes(x): if x == 1: return [] primes = set() while x != 1: p = spf[x] primes.add(p) while x % p == 0: x = x // p return sorted(primes) cnt = defaultdict(int) answer = 0 for num in A: primes = get_primes(num) k = len(primes) if k == 0: dp = 1 answer = (answer + dp) % MOD continue m_list = [] for mask in range(1, 1 << k): m = 1 for j in range(k): if mask & (1 << j): m *= primes[j] m_list.append(m) S = 0 for m in m_list: bits = bin(mask).count('1') # Wait, mask is not defined here. So need to track mask. # Alternative approach: for each (mask, m) pair, track the bits. # Alternatively, precompute bits for each mask. # To fix this, precompute the number of bits for each mask in m_list. # So, in the previous loop, store tuples (mask, m, bits) # But for efficiency, better precompute bits for each mask. # Rework the code to precompute bits for each mask in m_list m_list_with_bits = [] for mask in range(1, 1 << k): bits = bin(mask).count('1') m = 1 for j in range(k): if mask & (1 << j): m *= primes[j] m_list_with_bits.append((m, bits)) S = 0 for m, bits in m_list_with_bits: sign = (-1) ** (bits + 1) sum_m = cnt.get(m, 0) S += sign * sum_m S %= MOD dp = (1 + S) % MOD answer = (answer + dp) % MOD for m, bits in m_list_with_bits: cnt[m] = (cnt[m] + dp) % MOD print(answer % MOD) if __name__ == '__main__': main()