結果
問題 | No.2075 GCD Subsequence |
ユーザー | otoshigo |
提出日時 | 2022-09-17 16:36:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 591 ms / 4,000 ms |
コード長 | 2,727 bytes |
コンパイル時間 | 2,536 ms |
コンパイル使用メモリ | 209,024 KB |
実行使用メモリ | 19,820 KB |
最終ジャッジ日時 | 2024-06-01 15:14:35 |
合計ジャッジ時間 | 11,822 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 33 ms
11,164 KB |
testcase_01 | AC | 32 ms
11,168 KB |
testcase_02 | AC | 35 ms
11,144 KB |
testcase_03 | AC | 35 ms
11,348 KB |
testcase_04 | AC | 33 ms
11,120 KB |
testcase_05 | AC | 33 ms
11,048 KB |
testcase_06 | AC | 32 ms
11,144 KB |
testcase_07 | AC | 32 ms
11,288 KB |
testcase_08 | AC | 132 ms
19,472 KB |
testcase_09 | AC | 195 ms
19,784 KB |
testcase_10 | AC | 144 ms
19,300 KB |
testcase_11 | AC | 169 ms
19,504 KB |
testcase_12 | AC | 150 ms
19,528 KB |
testcase_13 | AC | 119 ms
19,392 KB |
testcase_14 | AC | 166 ms
19,580 KB |
testcase_15 | AC | 131 ms
19,452 KB |
testcase_16 | AC | 137 ms
19,432 KB |
testcase_17 | AC | 199 ms
19,748 KB |
testcase_18 | AC | 581 ms
19,792 KB |
testcase_19 | AC | 581 ms
19,688 KB |
testcase_20 | AC | 584 ms
19,688 KB |
testcase_21 | AC | 591 ms
19,784 KB |
testcase_22 | AC | 586 ms
19,720 KB |
testcase_23 | AC | 583 ms
19,820 KB |
testcase_24 | AC | 580 ms
19,688 KB |
testcase_25 | AC | 590 ms
19,600 KB |
testcase_26 | AC | 588 ms
19,744 KB |
testcase_27 | AC | 585 ms
19,704 KB |
testcase_28 | AC | 589 ms
12,148 KB |
testcase_29 | AC | 33 ms
11,288 KB |
testcase_30 | AC | 38 ms
11,152 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for (int i = 0; i < n; i++) #define rrep(i,n) for (int i = (n) - 1; i >= 0; i--) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} struct Eratosthenes{ vector<bool> prime; vector<int> factor, mobius; Eratosthenes(int n) : prime(n + 1, true), factor(n + 1, -1), mobius(n + 1, 1){ prime[1] = false; factor[1] = 1; for (int p = 2; p <= n; p++){ if (!prime[p]){ continue; } factor[p] = p; mobius[p] = -1; for (int q = 2 * p; q <= n; q += p){ prime[q] = false; factor[q] = p; if ((q / p) % p == 0){ mobius[q] = 0; } else{ mobius[q] = -mobius[q]; } } } } vector<pair<int, int>> factorize(int n){ vector<pair<int, int>> pf; while (n > 1){ int p = factor[n], exp = 0; while (n % p == 0){ n /= p; exp++; } pf.push_back(make_pair(p, exp)); } return pf; } vector<int> divisors(int n){ vector<int> div = {1}; vector<pair<int, int>> pf = factorize(n); for (auto [p, e] : pf){ int l = div.size(); for (int i = 0; i < l; i++){ int q = p; for (int j = 0; j < e; j++){ div.push_back(div[i] * q); q *= p; } } } //sort(div.begin(), div.end()); return div; } int euler(int n){ int e = n; vector<pair<int, int>> pf = factorize(n); for (int i = 0; i < pf.size(); i++){ e /= pf[i].first; e *= pf[i].first - 1; } return e; } }; const int MOD = 998244353; int n, A[200010]; ll S[1000010]; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cin >> n; ll s = 0; Eratosthenes er(1e6 + 1); rep(i, n){ cin >> A[i]; ll x = 1 + s; vector<int> div = er.divisors(A[i]); for (auto a : div){ x -= er.mobius[a] * S[a]; x %= MOD; if (x < 0){ x += MOD; } } s += x; s %= MOD; for (auto a : div){ S[a] += x; S[a] %= MOD; } } cout << s << "\n"; }