今回ABC最難だったりしない?
https://atcoder.jp/contests/abc230/tasks/abc230_g
問題
1~NのPermutation Pが与えられる。Pは1-originの配列とする。
(i,j)の対のうち、
- 1≦i<j≦N
- iとjは素でない
- P[i]とP[j]は素でない
ようなものは何通りか。
解法
メビウス関数を変形した以下の関数μ(n)を考える。
- nが奇数個の素数の積なら1
- nが偶数個の素数の積なら-1
- それ以外の場合(nが1か、4以上の平方数の倍数)は0
以下の関数を考える。
f(a,b,i,j) := iとjがaの倍数で、P[i]とP[j]がbの倍数なら1
解はとなる。
i,jを愚直に扱うと面倒なので、g(a,b) := iとjがaの倍数で、P[i]とP[j]がbの倍数なら1となる(i,j)の個数
とすると、解はとなる。
aを総当たりしたとき、bは総当たり不要で、P[i]の約数だけチェックすればよい。
なので、先にP[i]の約数を列挙しておくと割と速く処理できる。
int N,P[202020]; const int MA=202020; ll p[MA+1]; ll mu[MA+1]; vector<int> di[MA+1]; void solve() { int i,j,k,l,r,x,y; string s; for(i=2;i<=MA;i++) { mu[i]=-1; p[i]=i; } for(i=2;i<=MA;i++) if(p[i]==i) { for(j=i;j<=MA;j+=i) mu[j]=-mu[j], p[j]/=i; ll a=1LL*i*i; for(ll j=a;j<=MA;j+=a) mu[j]=0; } for(i=1;i<=MA;i++) if(mu[i]) { for(j=i;j<=MA;j+=i) di[j].push_back(i); } cin>>N; FOR(i,N) cin>>P[i+1]; ll ret=0; for(i=1;i<=N;i++) if(mu[i]) { map<int,int> num; for(j=i;j<=N;j+=i) { FORR(e,di[P[j]]) num[e]++; } FORR2(a,b,num) { ret+=mu[i]*mu[a]*b*(b+1)/2; } } cout<<ret<<endl; }
まとめ
Gも割としんどいけどHがなぁ。