容斥原理

设 U 中元素有 n 种不同的属性，而第 i 种属性称为$P_i$，拥有属性$P_i$的元素构成$S_i$，那么$\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^mS_{a_i}\right|$

容斥原理求不互质的数个数

inline void solve() {
    int n;
    while (cin >> n) {
        vector<int> a = {2, 5, 11, 13};
        int ans = n;
        for (int i = 1; i < 16; i++) {
            int cnt = 0, k = 1;
            for (int j = 0; j < 4; j++) {
                if ((i >> j) & 1) {
                    cnt++;
                    k *= a[j];
                }
            }
            if (cnt & 1)
                ans -= n / k;
            else
                ans += n / k;
        }
        cout << ans << endl;
    }
}