kmjp's blog

競技プログラミング参加記です

AtCoder ABC #230 : G - GCD Permutation

今回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
解は \displaystyle \sum_{1 \le i \lt j \le N}\sum_a \sum_b f(a,b,i,j)となる。

i,jを愚直に扱うと面倒なので、g(a,b) := iとjがaの倍数で、P[i]とP[j]がbの倍数なら1となる(i,j)の個数
とすると、解は \displaystyle \sum_a \sum_b \frac{g(a,b)(g(a,b)+1)}{2}となる。

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がなぁ。