容斥定理

两个集合的容斥关系公式：A∪B = A+B - A∩B

三个集合的容斥关系公式：A∪B∪C = A+B+C - A∩B - B∩C - C∩A +A∩B∩C

四个集合的容斥关系公式：A∪B∪C∪D = |A|+|B|+|C|+|D| - |A∩B| - |A∩C| - |A∩D|- |B∩C| - |B∩D| - |C∩D|
+|A∩B∩C|+|A∩B∩D| +|A∩C∩D| +|B∩C∩D| - |A∩B∩C∩D|

n个集合的容斥关系公式：|A1∪A2∪A3∪…∪An| = ∑|Ai1|-∑|Ai1∪Ai2|+…+（-1)^(k+1)∑|Ai1∪Ai2∪…∪Aik|

+…+（-1)^(n+1)∑|A1∪A2∪…∪An|

应用

1. 求10000以内不能被 2 3 5 整出的数

ans = n/2 + n/3 + n/5 + n/6 + n/10 + n/15 + n/30；

答案 = 10000 - ans

2. n封信对应n个信封，求恰好全部装错了信封的方案数

先讲一下全错排算法

要装第i封信的时候，先把前i-1个信全装错信封，然后随便选其中一个与第i封信交换，有i-1种选法

那么dp[i] = (i-1) * dp[i-1]

但是还有一种情况

要装第i封信的时候，先从i-1封信中任选i-2个信把他们全装错信封，然后把剩下的那个信与第i个交换，从i-1封信中任选i-2个信有i-1种选法

那么dp[i] = (i-1) * dp[i-2]

两个式子联合起来就是个递归的式子dp[i] = (i-1) * (dp[i-1] + dp[i-2])

然后讲一下容斥算法

首先，所有装信的总数是n！

A1表示1封信装对信封，数量是(n-1)! （只有n-1个位置可以乱放）

A2表示2封信装对信封，数量是(n-2)! （只有n-2个位置可以乱放）

...

An表示n封信装对信封，数量是1

那么这题的答案就是

n! - C(n, 1)*|A1| + C(n, 2)*|A2| - C(n, 3)*|A3| + ... + (-1)^n * C(n, n)*|A4|

化简

n! - n! / 1! + n! / 2! - n! / 3! + ... + (-1)^n * n! / n!

提取n!

n!(1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n * 1/n!)

3.给花盆涂色

给n盆花涂色，从m种颜色中选取k种颜色涂，保证正好用上k种颜色，你必须用上这k种颜色去涂满n个相邻的花，并且要求相邻花的颜色不同，求方案数。

(1 ≤ n, m ≤ 1e9 , 1 ≤ k ≤ 1e6 , k ≤ n, m)

首先，用k种颜色涂花，假如不考虑全部用上，那么总的方案数是多少

第一盆花有k种颜色选择，之后的花因为不能跟前一盆花的颜色相同，所以有k-1种选择

于是总方案数为k*(k-1)^(n-1)

因为题目问必须用上k种颜色

这里面包含了只用k-1种颜色的情况，应该减掉所有用k-1种的情况

减掉的东西里面，这里面包含了只用k-2种颜色的情况，应该加回来...

反反复复，最后就得出答案了

4.求(a,b)区间与n互质的数的个数

我们可以先求(1~b)区间的答案，然后减去(1~a-1)区间的答案

这样问题就转换为(1~m)区间与n互质的数的个数

互质的不好求，我们可以求不互质的个数，然后减一下

所有我们先求出n的所有质因数，然后用容斥做

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> p;
vector<ll>::iterator it;
vector<ll> v;
void init(ll x)
{
    p.clear();
    for(ll i =2;i*i<=x;i++)
    {
        if(x%i == 0){
            p.push_back(i);
            while(x%i == 0)
                x /= i;
        }
    }
    if(x>1)
        p.push_back(x);
    int v_size;
    v.clear();
    for(int i=0;i<p.size() ;i++)
    {
        v_size = v.size();
        for(int j=0;j<v_size;j++)
        {
            v.push_back(v[j] * p[i]);
        }
        v.push_back(p[i]);
    }
}
ll work(ll x)
{
    ll ans = x,flag = -1;
    for(int i=0;i<v.size();i++)
    {
        ans += flag*x/v[i];
        flag = -flag;
    }
    return ans;
}
int main()
{
    int t;
    ll l,r,n;
    cin>>t;
    while(t--)
    {
        cin>>l>>r>>n;
        init(n);
        cout<<work(r) - work(l-1)<<endl;
    }
    return 0;
}