結果
問題 |
No.2075 GCD Subsequence
|
ユーザー |
![]() |
提出日時 | 2025-08-19 10:13:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,813 bytes |
コンパイル時間 | 3,177 ms |
コンパイル使用メモリ | 279,496 KB |
実行使用メモリ | 14,696 KB |
最終ジャッジ日時 | 2025-08-19 10:13:35 |
合計ジャッジ時間 | 5,224 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 28 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, const char**)’: main.cpp:49:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 49 | freopen("explore.in", "r", stdin); | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:50:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 50 | freopen("explore.out", "w", stdout); | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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[]) { #ifndef LOCAL freopen("explore.in", "r", stdin); freopen("explore.out", "w", stdout); #endif optimizeIO(), cin >> n, init(); for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { dp = 1; 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; }