CF519 F - Make It One

Codeforces

良問だった

問題

n個の整数aが与えられる
aの部分集合のうち全要素のgcdが1になるようなもののサイズの最小値を求めよ
(存在しない場合は-1)

1 <= n <= 3*10^5
1 <= a[i] <= 3*10^5

解法

2*3*5*7*11*13 < 3*10^5 < 2*3*5*7*11*13*17
より答えはたかだか7であることがまずわかる
dp[i][j]: i個の要素を含み、それらのgcdがjになるような部分集合の個数
とすると包除原理より
dp[i][j] = (a[]のうちjで割り切れるものをi個選ぶ組み合わせの数) - Σdp[i][k] (k: jを除くjの倍数)
となる
d[i]: iで割り切れるa[j]の個数 を事前に求めておき、dpテーブルをjの降順に埋めていけばO(mlogm)で求められる
(m: max(a))
dp[i][1]>0を満たす最小のiが答え

int n, a[300300], b[300300], dp[10][300300], d[300300];

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> a[i];
		b[a[i]]++;
	}
	reps(i,1,300200) for (int j=i; j<=300200; j+=i) d[i] += b[j];
	reps(i,1,8) for (int j=300200; j>=1; j--) {
		dp[i][j] = comb(d[j], i);
		for (int k=j*2; k<=300200; k+=j) (dp[i][j] += mod - dp[i][k]) %= mod;
	}
	reps(i,1,8) if (dp[i][1]) return cout << i << endl ,0;
	cout << -1 << endl;
}

http://codeforces.com/contest/1043/problem/F