引入

求$1-1000$以内不能被$2、3、5$整除的数的个数。
经典的容斥题目，上来先甩一个柿子：$$ans=1000-[\frac{1000}{2}]-[\frac{1000}{3}]-[\frac{1000}{5}]+[\frac{1000}{2\times3}]+[\frac{1000}{2\times5}]+[\frac{1000}{3\times5}]-[\frac{1000}{2\times3\times5}]$$（[]表示高斯取整）（容斥没有不会的吧，不会的请回算法基础课重造谢谢）
但是我们发现一个问题：容斥在写的时候容易将正负号弄反，所以我们发明了莫比乌斯函数：$\mu(N)$

莫比乌斯函数

设$N=\prod_{i=1}^{k}{p_i^{\alpha_i}}$（$p_1,p_2,p_3 \dots $为质数数列）
$$ \mu(N)= \begin{cases} 1 , N = 1 \\\ (-1)^{k} , \alpha_1 = \alpha_2 = \dots = \alpha_k = 1 \\\ 0 , 存在至少一个{\alpha_i>1}也就是含有平方因子 \\\ \end{cases} $$
那这个莫比乌斯函数有啥用呢？表面上看这个函数就是在扯，但是我们会发现一件事情：$\mu(2)=-1 , \mu(3)=-1 , \mu(5)=-1 , \mu(2\times3)=1 \dots$，我们发现$\mu(k)$就是$[\frac{1000}{k}]$前的系数，所以下次写容斥的时候就不会写错了（但是这种方法只能用在为质数的情况，例如：$2,3,5$就为质数，故可以用莫比乌斯函数表示系数）

性质

莫比乌斯函数为积性函数（若函数$f(x)$满足当$gcd(a,b)=1$时$f(ab)=f(a) \times f(b)$，则函数$f(x)$为积性函数），证明如下（巨佬们可自行跳过）：
若已知$a,b$，且$(a,b)=1$，则$\mu(ab)$为：

1. $a = 1$，则$\mu(ab)=\mu(b)\times1=\mu(b) \times \mu(a)$
2. $b = 1$，则$\mu(ab)=\mu(a)\times1=\mu(a) \times \mu(b)$
3. $\mu(a)=0或\mu(b)=0$，那么$ab$中也有平方因子，所以$\mu(ab)=0$，则$\mu(ab)=\mu(a) \times \mu(b)$
4. 设$a = \prod_{i = 1}^{k_a}p_{i_a}^{\alpha_i}$，$b = \prod_{i = 1}^{k_b}p_{i_b}^{\beta_i}$，则$\mu(a)=(-1)^{k_a} , \mu(b)=(-1)^{k_b}$，又因为$(a,b)=1$，所以$\mu(ab)=(-1)^{k_a+k_b}=(-1)^{k_a} \times (-1)^{k_b} = \mu(a) \times \mu(b)$

莫比乌斯反演

啥都别讲，直接给出一个逝子$$F(N)=\sum_{d|N}f(d) \Leftrightarrow f(N)=\sum_{d|n}\mu(d)F(\frac{n}{d})$$
是不是懵了😵
那这个式子具体是啥意思呢？让我们看一下具体的描述：设$F(N)$和$f(N)$是定义在正整数集合上的两个函数,定义如下。
若$F(N)$函数满足：

$$F(N)=\sum_{d|N}f(d)$$

则有
$$f(N)=\sum_{d|N}\mu(d)F(\frac{N}{d})$$

那如何证明呢？事实上这个的证法要用迪利克雷卷积（其实还是本人太菜了，想不出别的又快又简洁又严谨的证法），而那个就是大学内容了，暂时不讲如何证明了，而且记下来莫比乌斯反演也挺简单的。

举例

我们可以举一个关于欧拉函数（$\varphi(N)）$的例子，令$f(N)=\varphi(N)$。
$$ 设N = \prod_{i=1}^{k}{p_i^{\alpha_i}}\\\ \varphi(N)\\\ = N\times\prod_{i=1}^{k}\frac{p_i-1}{p_i}\\\ = N \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \dots (1-\frac{1}{p_k})\\\ = N-\frac{N}{p_1}-\frac{N}{p_2}-\dots-\frac{N}{p_k}+\frac{N}{p_1 \times p_2}+\frac{N}{p_1 \times p_3}+\dots\\\ = \sum_{d|N}\mu(d)(\frac{N}{d})\\\\ 则可以令F(N)=N, 那么就能得到N=\sum_{d|N}\varphi(d) $$
那么$N=\sum_{d|N}\varphi(d)$到底对不对呢？证明如下：

Proof

记所有在$1-N$内的i满足$(i,N)=k$的$i$的个数为$C(N,k)$
显然$C(N,1)=\varphi(N)$
$\because (i,N)=k \Leftrightarrow (\frac{i}{k},\frac{N}{k})=1$
$\therefore C(N,k)=C(\frac{N}{k},1)=\varphi(\frac{N}{k})$
又$\because N=\sum_{d|N}{C(N,d)}$（对$(i,N)$的取值进行分类）
$\therefore N=\sum_{d|N}\varphi(\frac{N}{d})=\sum_{d|N}\varphi(d)$
证毕！

重点题目

例题一：洛谷P1390
莫比乌斯反演其实不难，唯一的难点在于寻找$F$与$f$。
题目要求$\sum_{i=1}^n \sum_{j=i+1}^n gcd(i,j)$，可以换个写法：设$f(d)$表示满足$gcd(i,j)=d$的数对$(i,j)$的数量，则$\sum_{i=1}^n \sum_{j=i+1}^n gcd(i,j) = \sum_{d=1}^n{d \times [(f(d)-1)\div 2]}$（还有$i<j$这个条件，所以要减$1$再除$2$），所以现在只要在可接受的时间复杂度内求出$f(d)$就可以了。
但是$f(d)$其实也不好求，于是一个经典思路就出现了：设$F(d)$表示表示满足$d|gcd(i,j)$的数对$(i,j)$的数量。
这个$F(d)$就好求了，为$(n\div d)^2$（想一想，为什么），那么如何用$F(d)$求$f(d)$呢？
考虑容斥，先将$F(d)$加进来，再减去公因数为$2d$的倍数的个数，也就是减去$F(2d)$，减去公因数为$2d$的倍数的个数，公因数为$6d$的倍数的个数减了两次要再加上$\dots$那么跟开头一样，$f(d)=F(d)-F(2d)-F(3d)+F(6d)\dots=\sum_{i=1}^{\frac{n}{i}}\mu(i)F(id)$

时间复杂度

$O(\frac{1}{n}+\frac{2}{n}+\dots+\frac{n}{n})=O(nln n)$

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
LL p[2000010],t,mo[2000010];//mo[i]：莫比乌斯函数
bool st[2000010];
void get_prime(LL x)//线性筛筛积性函数，大佬们用的一般是杜教筛，但本蒟蒻不会
{
    st[0]=st[1]=1;
    mo[1]=1;
    for(LL i=2;i<=x;i++){
        if(!st[i])p[++t]=i,mo[i]=-1;
        for(LL j=1;p[j]<=x/i;j++){
            st[i*p[j]]=1;
            if(i%p[j]==0){
                mo[i*p[j]]=0;
                break;
            }
            mo[i*p[j]]=mo[i]*mo[p[j]];
        }
    }
}
LL F(LL x)
{
    return (n/x)*(n/x);
}
int main()
{
    LL i,j,ans=0;
    cin>>n;
    get_prime(n);
    for(i=1;i<=n;i++){
        LL c=0;
        for(j=1;j<=n/i;j++)c+=mo[j]*F(j*i);
        ans+=(c-1)/2*i;
    }
    cout<<ans;
}

例题二 洛谷P2522/AcWing 2702

直接参照例题一的思路，$gcd(i,j)=k$不好求就求$k|gcd(i,j)$，但是这题有下界，于是我们有一个前缀和（理解为容斥也行）思路：设$sol(a,b)$为满足$1≤i≤a$且$1≤j≤b$且$gcd(i,j)=k$的数对$(i,j)$的个数，则答案为$sol(b,d)-sol(a-1,d)-sol(b,c-1)+sol(a-1,c-1)$。

于是就能写出代码了（抄袭党来此处复制🙃）

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,k;
int p[50010],t,mo[50010];
bool st[50010];
void get_prime(int x)
{
    st[0]=st[1]=1,mo[1]=1;
    for(int i=2;i<=x;i++){
        if(!st[i])p[++t]=i,mo[i]=-1;
        for(int j=1;p[j]<=x/i;j++){
            st[i*p[j]]=1;
            if(i%p[j]==0){
                mo[i*p[j]]=0;
                break;
            }
            mo[i*p[j]]=mo[p[j]]*mo[i];
        }
    }
}
int sol(int b,int d)
{
    int s=0,i;
    for(i=1;i<=min(b,d);i++)s+=mo[i]*(b/i)*(d/i);
    return s;
}
int main()
{
    int t,i;
    cin>>t;
    get_prime(50000);
    while(t--){
        cin>>a>>b>>c>>d>>k;
        cout<<sol(b/k,d/k)-sol((a-1)/k,d/k)-sol(b/k,(c-1)/k)+sol((a-1)/k,(c-1)/k)<<endl;
    }
}

结果发现$TLE$了，只得了$30$，$why?$
观察下数据范围，$n$为$50000$，$k$最小为$1$，$a,b,c,d$的最大值为$50000$，也就是最高会达到$50000 \times 50000$，妥妥的超时。
那如何优化呢？观察$F$函数，是用$[\frac{b}{i}]$与$[\frac{d}{i}]$组成的，看到这两个我们会想起什么？对了，就是二维数论分块，对$b,d$数论分块可将复杂度降至根号级别。

AC Code：

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,k;
int p[50010],t,mo[50010],sum[50010];
bool st[50010];
void get_prime(int x)
{
    st[0]=st[1]=1,mo[1]=1;
    for(int i=2;i<=x;i++){
        if(!st[i])p[++t]=i,mo[i]=-1;
        for(int j=1;p[j]<=x/i;j++){
            st[i*p[j]]=1;
            if(i%p[j]==0){
                mo[i*p[j]]=0;
                break;
            }
            mo[i*p[j]]=mo[p[j]]*mo[i];
        }
    }
    for(int i=1;i<=x;i++)sum[i]=sum[i-1]+mo[i];
}
int sol(int b,int d)
{
    int s=0,l=1,r1,r2,r;
    while(l<=min(b,d)){//二维数论分块
        r1=b/(b/l);
        r2=d/(d/l);
        r=min(r1,r2);
        s+=(sum[r]-sum[l-1])*(b/r)*(d/r);
        l=r+1;
    }
    return s;
}
int main()
{
    int t,i;
    cin>>t;
    get_prime(50000);
    while(t--){
        cin>>a>>b>>c>>d>>k;
        cout<<sol(b/k,d/k)-sol((a-1)/k,d/k)-sol(b/k,(c-1)/k)+sol((a-1)/k,(c-1)/k)<<endl;
    }
}

难题

洛谷P2231/AcWing.2098
当然，这题可以用DP，但是我们来讲一个莫比乌斯反演的做法。
设卡片上的数为$x_1,x_2 \dots x_{n+1}$，则此卡片满足要求的充分必要条件为存在一组数$a_1,a_2 \dots a_{n+1}$，使得$a_1 x_1 + a_2 x_2 + \dots a_{n+1} x_{n+1} = 1$，由裴蜀定理易得充分必要条件等价于$gcd(x_1,x_2 \dots x_{n+1}) = 1$。
而公约数为$1$是极困难的，考虑正难则反。
设$gcd(x_1,x_2 \dots x_{n+1}) = d$，又$\because x_{n+1}=m$，$\therefore d|m$，因此可以枚举$d$，所以答案就不难写出：
$$ m^n+\sum_{d|m,d>1} \mu(d)(\frac{m}{d})^n \\\ =\sum_{d|m} \mu(d)(\frac{m}{d})^n \\\ =m^n*\sum_{d|m} \mu(d)\frac{1}{d^n} \\\ 令m=\prod_{i=1}^k {p_i}^{\alpha_i}. \\\ 答案=m^n * \prod_{i=1}^k (1-\frac{1}{p_i^n}) $$
代码自行实现

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m;
LL qmi(LL a,LL b)
{
    LL ans=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int main()
{
    LL i;
    cin>>n>>m;
    LL ans=qmi(m,n);
    for(i=2;i<=m/i;i++)
        if(m%i==0){
            LL s=qmi(i,n);
            ans/=s,ans*=s-1;
            while(m%i==0)m/=i;
        }

    if(m>1){
        LL s=qmi(m,n);
        ans/=s,ans*=s-1;
    }
    cout<<ans;
}