結果
問題 | No.2075 GCD Subsequence |
ユーザー |
![]() |
提出日時 | 2023-03-14 12:16:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,768 ms / 4,000 ms |
コード長 | 3,325 bytes |
コンパイル時間 | 3,980 ms |
コンパイル使用メモリ | 256,064 KB |
最終ジャッジ日時 | 2025-02-11 11:06:04 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using ll=long long;using ld=long double;ld pie=3.141592653589793;ll inf=15555055;ll mod=998244353;struct Eratosthenes {// テーブルvector<bool> isprime;// 整数 i を割り切る最小の素数vector<ll> minfactor;vector<ll>mobius;// コンストラクタで篩を回すEratosthenes(ll N) : isprime(N+1, true),minfactor(N+1, -1),mobius(N+1,1) {// 1 は予めふるい落としておくisprime[1] = false;minfactor[1] = 1;// 篩for (ll p = 2; p <= N; ++p) {// すでに合成数であるものはスキップするif (!isprime[p]) continue;// p についての情報更新minfactor[p] = p;mobius[p]=-1;// p 以外の p の倍数から素数ラベルを剥奪for (ll q = p * 2; q <= N; q += p) {// q は合成数なのでふるい落とすisprime[q] = false;// q は p で割り切れる旨を更新if (minfactor[q] == -1) minfactor[q] = p;if ((q / p) % p == 0) mobius[q] = 0;else mobius[q] = -mobius[q];}}}// 高速素因数分解// pair (素因子, 指数) の vector を返すvector<pair<ll,ll>> factorize(ll n) {vector<pair<ll,ll>> res;while (n > 1) {ll p = minfactor[n];ll exp = 0;// n で割り切れる限り割るwhile (minfactor[n] == p) {n /= p;++exp;}res.emplace_back(p, exp);}return res;}vector<ll>divisors(ll n){vector<ll>res({1});auto pf=factorize(n);for (auto p : pf){ll s=(ll)res.size();for (ll i = 0; i < s; i++){ll v=1;for (ll j = 0; j < p.second; j++){v*=p.first;res.push_back(res[i]*v);}}}return res;}};int main(){ll n;cin >> n;vector<ll>a(n);for (ll i = 0; i < n; i++){cin >> a[i];}vector<ll>memo(1000001,0);Eratosthenes er(1000001);ll ans=0;memo[1]=1;for (ll i = 0; i < n; i++){if (a[i]==1){ans+=1;ans%=mod;continue;}vector<ll>x=er.divisors(a[i]);ll now=0;for (ll j = 0; j < x.size(); j++){if (x[j]==1){now+=1;now%=mod;continue;}now+=(-er.mobius[x[j]]*memo[x[j]])%mod;now%=mod;}now%=mod;now+=mod;now%=mod;ans+=now;ans%=mod;for (ll j = 0; j < x.size(); j++){if (x[j]!=1&&er.mobius[x[j]]!=0){memo[x[j]]+=now;memo[x[j]]%=mod;}}}cout << ans << endl;}