結果
問題 |
No.2075 GCD Subsequence
|
ユーザー |
![]() |
提出日時 | 2025-08-19 10:11:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,763 bytes |
コンパイル時間 | 3,261 ms |
コンパイル使用メモリ | 281,600 KB |
実行使用メモリ | 18,152 KB |
最終ジャッジ日時 | 2025-08-19 10:11:47 |
合計ジャッジ時間 | 9,268 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | WA * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int N = 1000010; const int P = 998244353; using u64 = unsigned long long; int n, dp, a[N], minp[N], cnt[N], sum[N]; inline void init(void) { std::vector<int> P; for (int i = 2; i < N; i++) { if (minp[i] == 0) { P.push_back(i); minp[i] = i, cnt[i] = 1; } for (auto &p : P) { if (i * p >= N) break; minp[i * p] = p; if (i % p == 0) { cnt[i * p] = cnt[i]; break; } else { cnt[i * p] = cnt[i] + 1; } } } } std::vector<int> comp(int x) { std::vector<int> fac; fac.reserve(cnt[x]); while (x > 1) { int cur = minp[x]; fac.push_back(cur); while (x % cur == 0) x /= cur; } int m = fac.size(); std::vector<int> ret(1 << m, 1); for (int S = 1; S < (1 << m); S++) { const int hb = std::__lg(S); ret[S] = ret[S ^ (1 << hb)] * fac[hb]; } return ret; } inline void optimizeIO(void) { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); } inline int sgn(int x) { return x & 1 ? 1 : P - 1; } int main(int argc, char const *argv[]) { optimizeIO(), cin >> n, init(), dp = 1; for (int i = 1; i <= n; i++) cin >> a[i]; for (auto &x : comp(a[1])) sum[x] = 1; for (int i = 2; i <= n; i++) { dp = 0; auto res = comp(a[i]); for (size_t S = 1; S < res.size(); S++) { int p = __builtin_popcount(S); dp = (dp + 1ll * sgn(p) * sum[res[S]]) % P; } for (auto &x : res) { sum[x] += dp; if (sum[x] >= P) sum[x] -= P; } } cout << dp << endl; return 0; }