結果
問題 | No.1760 Setwise Coprime |
ユーザー | chocorusk |
提出日時 | 2021-11-20 13:49:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,812 bytes |
コンパイル時間 | 4,112 ms |
コンパイル使用メモリ | 191,184 KB |
実行使用メモリ | 31,852 KB |
最終ジャッジ日時 | 2023-09-02 07:42:49 |
合計ジャッジ時間 | 32,220 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
14,516 KB |
testcase_01 | AC | 9 ms
14,296 KB |
testcase_02 | AC | 15 ms
14,660 KB |
testcase_03 | AC | 8 ms
14,284 KB |
testcase_04 | AC | 9 ms
14,372 KB |
testcase_05 | AC | 8 ms
14,384 KB |
testcase_06 | AC | 14 ms
14,508 KB |
testcase_07 | AC | 12 ms
14,356 KB |
testcase_08 | AC | 12 ms
14,376 KB |
testcase_09 | AC | 14 ms
14,552 KB |
testcase_10 | AC | 10 ms
14,320 KB |
testcase_11 | AC | 15 ms
14,444 KB |
testcase_12 | AC | 12 ms
14,388 KB |
testcase_13 | AC | 10 ms
14,344 KB |
testcase_14 | AC | 14 ms
14,464 KB |
testcase_15 | AC | 12 ms
14,380 KB |
testcase_16 | AC | 15 ms
14,524 KB |
testcase_17 | AC | 14 ms
14,436 KB |
testcase_18 | AC | 10 ms
14,332 KB |
testcase_19 | AC | 12 ms
14,368 KB |
testcase_20 | AC | 12 ms
14,392 KB |
testcase_21 | AC | 1,550 ms
27,932 KB |
testcase_22 | AC | 1,320 ms
26,192 KB |
testcase_23 | AC | 1,819 ms
29,916 KB |
testcase_24 | AC | 642 ms
20,944 KB |
testcase_25 | AC | 1,531 ms
27,784 KB |
testcase_26 | AC | 1,069 ms
24,336 KB |
testcase_27 | AC | 376 ms
18,760 KB |
testcase_28 | AC | 157 ms
16,300 KB |
testcase_29 | AC | 1,903 ms
30,444 KB |
testcase_30 | AC | 1,898 ms
30,328 KB |
testcase_31 | AC | 471 ms
19,472 KB |
testcase_32 | AC | 1,692 ms
28,940 KB |
testcase_33 | AC | 1,035 ms
24,152 KB |
testcase_34 | AC | 1,896 ms
30,272 KB |
testcase_35 | AC | 1,431 ms
27,064 KB |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; using mint=modint998244353; const int MAX=200020; bitset<MAX> isprime; void sieve(){ for(int i=3; i<MAX; i++, i++) isprime[i]=1; isprime[2]=1; for(int i=3; i<MAX; i++){ if(isprime[i]){ for(int j=(i<<1); j<MAX; j+=i) isprime[j]=0; } } } vector<int> vd[200020]; int m[200020]; int main() { int n;cin>>n; for(int d=1; d<=n; d++){ for(int i=d; i<=n; i+=d) vd[i].push_back(d); } sieve(); fill(m+1, m+n+1, 1); for(int i=2; i<=n; i++){ if(!isprime[i])continue; for(int j=i; j<=n; j+=i){ if(j%((ll)i*i)==0){ m[j]=0; } m[j]=-m[j]; } } mint x[200020]; for(int i=1; i<=n; i++){ x[i]=mint(m[i])*(mint(2).pow(n/i)); } mint ans=0; mint q[200020]; for(int i=1; i<=n; i++){ q[i]=m[i]*(mint(2).pow(n/i)-1); ans+=q[i]; } ans=ans*ans; mint y[200020], z[200020], w[200020]; for(int i=1; i<=n; i++){ for(auto d1:vd[i]){ for(auto d2:vd[i]){ if(lcm(d1, d2)<i)continue; y[i]+=x[d1]*x[d2]; z[i]+=x[d1]*m[d2]; //w[i]+=m[d1]*m[d2]; } } } mint p2[200020], p3[200020], p4[200020]; p2[0]=1,p3[0]=1,p4[0]=1; for(int i=1; i<=n; i++){ p2[i]=p2[i-1]*2; p3[i]=p3[i-1]*3; p4[i]=p4[i-1]*4; } for(int i=1; i<=n; i++){ ans+=y[i]/p4[n/i]; ans-=2*z[i]/p2[n/i]; ans+=2*z[i]; ans-=y[i]; //ans+=w[i]; ans+=2*(p2[n/i]-1)*(y[i]/p4[n/i]); ans-=2*(p2[n/i]-1)*z[i]/p2[n/i]; ans+=(p3[n/i]-2*p2[n/i]+1)*y[i]/p4[n/i]; } cout<<ans.val()<<endl; // mint ans1=0; // for(int i=1; i<=n; i++){ // for(int j=1; j<=n; j++){ // int l=lcm(i,j); // mint a=mint(2).pow(n/i-n/l)-1; // mint b=mint(2).pow(n/j-n/l)-1; // ans1+=m[i]*m[j]*a*b; // ans1+=m[i]*m[j]*2*(mint(2).pow(n/l)-1)*(a+1)*b; // ans1+=m[i]*m[j]*(mint(3).pow(n/l)-2*mint(2).pow(n/l)+1)*(a+1)*(b+1); // } // } // cout<<ans1.val()<<endl; return 0; }