Codeforces #305 Div1 C. Mike and Foam

なんとか本番解けた。
http://codeforces.com/contest/547/problem/C

問題

N要素の整数A[i]がある。
また整数集合Sを考える。Sは初期状態で空である。

ここでQ個のクエリが与えられる。
各クエリでは整数列中の添え字xが指定される。
S中にxが無ければxを追加し、xがあればxを取り除く。

各クエリ毎に、S中の整数ペア(i,j)のうちGCD(A[i],A[j])==1となるものの数を求めよ。

解法

S中の整数ペアの数は|S|*(|S|-1)/2なので、そこからGCD(A[i],A[j])＞1となるものの数を引くことを考える。

S中の各xについて、2～max(A)の各素数を素因数に持つA[x]が何個ずつあるかを管理する。

クエリ毎にA[x]を素因数分解する。
その上で、前述の管理データから、S中に同じ素因数を持つ数字が他に何個あるか数え上げる。
その際、複数の素因数が重複するものを多重にカウントしないよう、包除原理の要領で数え上げていく。

vector<ll> enumdiv(ll n) {
	vector<ll> V;
	for(ll i=2;i*i<=n;i++) {
		if(n%i==0) V.push_back(i);
		while(n%i==0) n/=i;
	}
	if(n>1) V.push_back(n);
	return V;
}

int N,Q;
int A[202000];
int on[202000];
ll non;
int num[502000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	ll tot=0;
	
	while(Q--) {
		cin>>x;
		x--;
		
		vector<ll> V=enumdiv(A[x]);
		int bn=V.size();
		on[x]^=1;
		for(int mask=1;mask<1<<bn;mask++) {
			int odd=1;
			int n=1;
			FOR(i,bn) if(mask & (1<<i)) odd*=-1, n*=V[i];
			if(on[x]) {
				tot += odd*num[n];
				num[n]++;
			}
			else {
				tot -= odd*(--num[n]);
			}
		}
		
		if(on[x]) non++;
		else non--;
		cout<<non*(non-1)/2 + tot<<endl;
	}
}

まとめ

包除原理は苦手だったので、なんとか解ききれて良かったね。