結果
問題 | No.2075 GCD Subsequence |
ユーザー |
|
提出日時 | 2023-07-12 08:31:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,347 ms / 4,000 ms |
コード長 | 2,483 bytes |
コンパイル時間 | 1,426 ms |
コンパイル使用メモリ | 108,040 KB |
最終ジャッジ日時 | 2025-02-15 09:58:27 |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
/*余事象2055*/#include<iostream>#include<set>#include<algorithm>#include<vector>#include<string>#include<set>#include<map>#include<numeric>#include<queue>#include<cmath>using namespace std;typedef long long ll;const ll INF=1LL<<60;typedef pair<int,int> P;typedef pair<int,P> PP;const ll MOD=998244353;const double PI=acos(-1);struct Mobius{std::vector<int> lists;std::vector<bool> isprime;int n;Mobius(int n_):n(n_){lists=std::vector<int>(n+1,1);isprime=std::vector<bool>(n+1,true);init();}void init(){isprime[0]=isprime[1]=false;for(long long i=2;i<=n;i++){if(!isprime[i]) continue;//iが素数でない場合lists[i]=(-1)*lists[i];for(long long j=2*i;j<=n;j+=i){isprime[j]=false;if( ((j/i)%i)==0 ){//jは (i*i)で割れるlists[j]=0;}lists[j]*=(-1);}}}int operator()(int n){return lists[n];}};Mobius mobius(1e6+10);int main(){int N;cin>>N;vector<ll> A(N);for(int i=0;i<N;i++){cin>>A[i];}//map<ll,ll> dp;//map<ll,ll> g;vector<ll> dp(1000000+10,0);vector<ll> g(1000000+10,0);ll tot=0;for(int i=0;i<N;i++){vector<ll> d;for(ll x=1;x*x<=A[i];x++){if(A[i]%x==0){d.push_back(x);if(A[i]/x!=x){d.push_back(A[i]/x);}}}ll f1=0;for(ll x:d){//f1+=g[x]*mobius(x);if(mobius(x)>0){f1+=g[x]%MOD;f1%=MOD;}else if(mobius(x)<0){f1+=(MOD-g[x])%MOD;f1%=MOD;}}//ll add=1+tot-f1;ll add=0;add+=1;add%=MOD;add+=tot;add%=MOD;add+=(MOD-f1)%MOD;add%=MOD;dp[A[i]]+=add;dp[A[i]]%=MOD;tot+=add;tot%=MOD;for(ll x:d){//A[i]はxで割れるg[x]+=add;g[x]%=MOD;}}ll ans=0;// for(auto [key,val]:dp){// ans+=val;// ans%=MOD;// }for(int i=1;i<=1000000;i++){ans+=dp[i];ans%=MOD;}cout<<ans<<endl;}