Codeforces #519 F. Make It One

これははまりすぎた…。
http://codeforces.com/contest/1043/problem/F

問題

整数集合Aが与えられる。
これらの要素のうちいくつかを選びGCDが1となるようにしたい。
最小何個選べばよいか。

解法

Aの上限より、各要素は素因数分解すると高々6個の素因数しか持たない。
AのGCDが1であれば、Aから最大7要素を選べば必ずGCDを1にできる。

それはそうとして、以下を考える。
f(n,k) := Aからn個の要素を選んだ時、GCDがちょうどkとなる組み合わせ数

B(i) := Aのうちiの倍数の個数
とすると

なので、f(n,k)をnが7以下、kが300000以下の範囲で求めていこう。
f(n,1)が正となる最小のnが解となる。

int N;
int A[303030];

ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll dp[8][303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int G=0;
	FOR(i,N) {
		cin>>x;
		A[x]++;
	}
	for(i=1;i<=300000;i++) {
		for(j=2*i;j<=300000;j+=i) A[i]+=A[j];
	}
	
	for(i=1;i<=7;i++) {
		for(x=300000;x>=1;x--) {
			dp[i][x]=comb(A[x],i);
			for(j=2*x;j<=300000;j+=x) dp[i][x]-=dp[i][j];
			dp[i][x]=(dp[i][x]%mo+mo)%mo;
		}
		if(dp[i][1]) return _P("%d\n",i);
	}
	cout<<-1<<endl;
	
}

まとめ

包除原理に頭がいかなかった…。