alan23273850 的刷題筆記
d444: 排容原理
Tags: bitmask, combinatorics
出處：https://zerojudge.tw/ShowProblem?problemid=d444
提交：https://zerojudge.tw/Submissions?problemid=d444&account=allllllan123456
問題：給定 $M\in[1,15]$ 個 (自己或全部乘起來) 皆在 int 範圍內的正整數 $S[i]$，以及一個 int 的正整數上界 $N$，請求出 1 ~ $N$ 內把所有 $S[i]$ 的倍數 (含本身) 都扣掉之後剩餘數字的個數。
解法：如題，就是應用排容原理，對於任取一個數字的倍數用相減，任取兩個數字的公倍數用相加，任取三個數字的公倍數用相減，依此類推，直到任取 $M$ 個數字的倍數計算完畢就是答案。這題可搭配 DFS 與 bitmask 來完成，實作上非常簡潔愉悅。
1#include <bits/stdc++.h>
2using namespace std;
3
4int sum, N, M, S[15];
5
6void dfs(int index, int lcm, unsigned config) {
7 if (index && config>>index-1) sum += (1 - (__builtin_popcount(config) & 1) * 2) * N / lcm;
8 if (index == M) return;
9 dfs(index + 1, lcm * S[index] / __gcd(lcm, S[index]), config | 1<<index);
10 dfs(index + 1, lcm, config);
11}
12
13int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
14 while (cin >> N >> M && (N||M)) {
15 for (int i=0; i<M; i++) cin >> S[i];
16 sum = N; dfs(0, 1, 0);
17 cout << sum << '\n';
18 }
19 return 0;
20}