みんなのプロコン2018 決勝 A - Uncommon

包除原理マスターになりたい

問題

n個の相異なる整数aと整数mが与えられる
1以上m以下のそれぞれの整数iについて、aのうちiと互いに素であるものの個数を求めよ

1 <= n, m <= 10^5
1 <= a[i] <= 10^5

解法

xと互いに素な数 ってのは xの素因数のどれでも割り切れないような数 と言い換えられる
「xの相異なる素因数の集合」のある部分集合をSとし、
f(S): Sの全要素で割り切れるような数の個数
とすると、包除原理より答えは
Σ f(S) * (-1)^|S|
となる
f(S)はO(nlogn)で事前計算可能
10^5以下の自然数の相異なる素因数はたかだか6個しかないから、Sは全通り試しても十分高速に計算できる

int n, m, a[100100], d[100100];
set<int> s;

vector<int> pf(int n) {
	vector<int> res;
	for (int i = 2; i*i <= n; i++) if (n%i==0) {
		res.push_back(i);
		while (n%i==0) n /= i;
	}
	if (n!=1) res.push_back(n);
	return res;
}

signed main() {
	cin >> n >> m;
	rep(i,n) {
		cin >> a[i];
		s.insert(a[i]);
	}
	reps(i,1,m+1) {
		for(int j=i; j<100100; j+=i) if (s.count(j)) d[i]++;
		vector<int> p = pf(i);
		int res = 0;
		rep(j,1<<p.size()) {
			int num = 1;
			rep(k,p.size()) if (j>>k&1) num *= p[k];
			if (__builtin_parity(j)) res -= d[num];
			else res += d[num];
		}
		cout << res << endl;
	}
}