結果
問題 | 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; }