数学 _ 容斥原理

概述

引子：
如何计算这个图形的面积？

很显然：

\[|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C| \]

把上述问题推广到一般情况，就是我们熟知的容斥原理。

定义：
设 U 中元素有 m 种不同的属性，而第 i 种属性称为\(P_i\) ，拥有属性 \(P_i\) 的元素构成集合\(S_i\)，那么，集合\(S_i\)的并为：
\(\bigcup_{i=1}^{m} S_i=S_1+S_2 + \ldots + S_m\)
\(\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,- (S_1 \bigcap S_2+S_1 \bigcap S_3+\ldots + S_{m-1} \bigcap S_m)\)
\(\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+(S_1 \bigcap S_2 \bigcap S_3+\ldots + S_{m-2} \bigcap S_{m-1} \bigcap S_m)\)
\(\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+ \ldots + (-1)^{m - 1}(\bigcap_{i=1}^{m}S)\)

复杂度：\(O(2^m)\)

补集
对于全集 U 下的 集合的并 可以使用容斥原理计算，而 集合的交 则用全集减去 补集的并集 求得

\[\bigcap_{i=1}^{n}S_i = U- \bigcup_{i=1}^n\overline{S_i} \]

原文

应用

区间[L,R]中与 k 互质的数的个数

原文
复杂度: \(O(2^{fac[k]})\) 其 中 \(fac[k]\) 为 \(k\) 的质因子的种类数。

当fac[k]为10时（时间复杂度才1e3），k就已经大于\(1e9\)了

结论就是1e18的范围内，都可以算出来。

namespace qjhz {
    typedef long long LL;
    int T, N, num;
    LL A, B;
    int a[100];
    void prime(int n) {
        num = 0;
        for (int i = 2; i*i <= n; i++) {
            if ((n%i) == 0) {
                num++;
                a[num] = i;
                while ((n%i) == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) {
            num++;
            a[num] = n;
        }
        return;
    }
    LL solve(LL r, int n) {
        prime(n);
        LL res = 0;
        for (int i = 1; i < (1 << num); i++) {
            int kk = 0;
            LL div = 1;
            for (int j = 1; j <= num; j++) {
                if (i&(1 << (j - 1))) {
                    kk++;
                    div *= a[j];
                }
            }
            if (kk % 2)
                res += r / div;
            else
                res -= r / div;
        }
        return r - res;

    }

    LL que(LL L, LL R, LL k) {
        return solve(R, k) - solve(L - 1, k);
    }
}

void slove() {
    int a, m; cin >> a >> m;
    int g = gcd(a, m);
    int L = a / g, R = (a + m - 1) / g;
    cout << qjhz::que(L, R, m / g) << endl;
}