みんなのプロコン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; } }