結果
問題 | No.2075 GCD Subsequence |
ユーザー |
![]() |
提出日時 | 2023-08-06 07:29:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 815 ms / 4,000 ms |
コード長 | 1,813 bytes |
コンパイル時間 | 5,948 ms |
コンパイル使用メモリ | 318,184 KB |
実行使用メモリ | 22,812 KB |
最終ジャッジ日時 | 2024-11-06 10:27:17 |
合計ジャッジ時間 | 20,996 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using mint=modint998244353; //1000000007;using ll=long long;using pp=pair<int,int>;#define sr string#define vc vector#define fi first#define se second#define rep(i,n) for(int i=0;i<(int)n;i++)#define pb push_back#define all(v) v.begin(),v.end()#define pque priority_queue#define bpc(a) __builtin_popcount(a)struct divs{int n;vector<int> f, primes;divs(int n=1):n(n), f(n+1) {f[0] = f[1] = -1;for (ll i = 2; i <= n; ++i) {if (f[i]) continue;primes.push_back(i);f[i] = i;for (ll j = i*i; j <= n; j += i) {if (!f[j]) f[j] = i;}}}bool isPrime(int x) { return f[x] == x;}vector<int> factorList(int x) {vector<int> res;while (x != 1) {res.push_back(f[x]);x /= f[x];}return res;}vector<pair<int,int>> factor(int x) {vector<int> fl = factorList(x);if (fl.size() == 0) return {};vector<pair<int,int>> res(1, pair<int,int>(fl[0], 0));for (int p : fl) {if (res.back().first == p) {res.back().second++;} else {res.emplace_back(p, 1);}}return res;}vc<int>mev(int x){auto fl=factor(x);vc<int>res;for(auto [a,z]:fl){for(int i=res.size()-1;i>=0;i--)res.pb(res[i]*a);res.pb(a);}return res;}};int main(){int n;cin>>n; int m=1e6;vc<int>v(n); rep(i,n)cin>>v[i];map<int,mint>mp;vc<int>mv(m+1,-1);divs d(m);for(ll au:d.primes)for(ll i=au*au;i<=m;i+=au*au)mv[i]=0;for(auto au:d.primes)for(int i=au;i<=m;i+=au)mv[i]*=-1;mint ans=0;rep(i,n){int a=v[i];mint now=1;for(auto au:d.mev(a))now+=mv[au]*mp[au];for(auto au:d.mev(a))mp[au]+=now;ans+=now;}cout<<ans.val();}