結果
問題 | No.2075 GCD Subsequence |
ユーザー | HIcoder |
提出日時 | 2023-07-12 08:31:19 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,490 ms / 4,000 ms |
コード長 | 2,483 bytes |
コンパイル時間 | 1,054 ms |
コンパイル使用メモリ | 109,324 KB |
実行使用メモリ | 24,416 KB |
最終ジャッジ日時 | 2023-10-11 22:35:00 |
合計ジャッジ時間 | 42,812 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 82 ms
22,660 KB |
testcase_01 | AC | 82 ms
22,632 KB |
testcase_02 | AC | 81 ms
22,660 KB |
testcase_03 | AC | 83 ms
22,652 KB |
testcase_04 | AC | 83 ms
22,900 KB |
testcase_05 | AC | 82 ms
22,668 KB |
testcase_06 | AC | 81 ms
22,676 KB |
testcase_07 | AC | 84 ms
22,648 KB |
testcase_08 | AC | 1,014 ms
23,408 KB |
testcase_09 | AC | 1,629 ms
24,164 KB |
testcase_10 | AC | 1,066 ms
23,652 KB |
testcase_11 | AC | 1,398 ms
24,060 KB |
testcase_12 | AC | 1,206 ms
23,796 KB |
testcase_13 | AC | 900 ms
23,512 KB |
testcase_14 | AC | 1,363 ms
23,972 KB |
testcase_15 | AC | 959 ms
23,452 KB |
testcase_16 | AC | 1,017 ms
23,712 KB |
testcase_17 | AC | 1,614 ms
24,244 KB |
testcase_18 | AC | 2,445 ms
24,192 KB |
testcase_19 | AC | 2,454 ms
24,244 KB |
testcase_20 | AC | 2,448 ms
24,184 KB |
testcase_21 | AC | 2,441 ms
24,116 KB |
testcase_22 | AC | 2,448 ms
24,416 KB |
testcase_23 | AC | 2,446 ms
24,384 KB |
testcase_24 | AC | 2,441 ms
24,244 KB |
testcase_25 | AC | 2,443 ms
24,172 KB |
testcase_26 | AC | 2,446 ms
24,308 KB |
testcase_27 | AC | 2,454 ms
24,308 KB |
testcase_28 | AC | 2,490 ms
24,136 KB |
testcase_29 | AC | 83 ms
22,652 KB |
testcase_30 | AC | 80 ms
22,660 KB |
ソースコード
/* 余事象 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; }