Codeforces ECR #020 : F. Coprime Subsequences

今回は割とすんなり解けて好順位だったのでよかったね。
http://codeforces.com/contest/803/problem/F

問題

N要素の整数列Aが与えられる。
Aのsubsequenceのうち、最大公約数が1のものは何通りあるか。

解法

包除原理の要領でとく。
整数kの倍数がA中にf(k)個あるなら、最大公約数がkの倍数になる組み合わせg(k)はf(k)個から1個以上選ぶ2^(f(k))-1通りとなる。
そこから、kより大きなkの倍数ができてしまうケースg(ik) (i＞1)を引いていけばよい。

int N,A;
ll mo=1000000007;

int num[101010];
ll p2[101010];
ll pat[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,101000) p2[i+1]=p2[i]*2%mo;
	
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		num[x]++;
	}
	for(i=1;i<=100000;i++) {
		for(j=i*2;j<=100000;j+=i) num[i]+=num[j];
		pat[i]=(p2[num[i]]+mo-1)%mo;
	}
	for(i=100000;i>=1;i--) {
		for(j=i*2;j<=100000;j+=i) pat[i]-=pat[j];
		pat[i]=(pat[i]%mo+mo)%mo;
	}
	cout<<pat[1]<<endl;
}

まとめ

これはさっくり解けてよかったね。