莫比乌斯反演

一.莫比乌斯函数：

1.定义：

μ(d)=⎩⎪⎨⎪⎧​1,(−1)k,0,​d=1d=p1​∗p2​∗...∗pk​,p1​,p2​,...均为互异质数其他情况​

2.性质：

(1) 积性函数，即如果满足 $a$a 和 $b$b 互质，那么就会满足 $f(a\ast b)=f\left(a\right)\ast f\left(b\right)$f(a∗b)=f(a)∗f(b)；

(2) 对任意的正整数 $n$n ,当 $n>1$n>1时，其所有因子的莫比乌斯函数值相加为0，
即：
d∣n∑​μ(d)={1,0,​ n=1 n>1​
证明：
当 $n=1$n=1 时，显然成立；
当 $n>1$n>1 时，
首先，有：
$\mu \left(d\right)\ne 0⟺d=p_1\ast p_2\ast ...\ast p_k$μ(d)​=0⟺d=p1​∗p2​∗...∗pk​
对于 $\mu \left(d\right)=0$μ(d)=0 的因子，我们可以不用考虑，下面仅对 $\mu \left(d\right)\ne 0$μ(d)​=0 的因子讨论。
那么对于一个含有 $r$r 的质因子的因子 $d$d， $\mu \left(d\right)=C_k^r\ast (-1{)}^r$μ(d)=Ckr​∗(−1)r。
所以
$\sum _{d\mid n}\mu \left(d\right)=\sum _{i=0}^k{C}_k^i\ast (-1{)}^i$d∣n∑​μ(d)=i=0∑k​Cki​∗(−1)i
又根据二项式定理：
$(x+y{)}^n=\sum _{i=0}^n{C}_n^i\ast x^i\ast y^{n-i}$(x+y)n=i=0∑n​Cni​∗xi∗yn−i
令 $x=-1,y=1$x=−1,y=1，有
$\sum _{i=0}^k{C}_k^i\ast (-1{)}^i=\sum _{i=0}^k{C}_k^i\ast x^i\ast y^{k-i}=0$i=0∑k​Cki​∗(−1)i=i=0∑k​Cki​∗xi∗yk−i=0
所以，
$\sum _{d\mid n}\mu \left(d\right)=0$d∣n∑​μ(d)=0
即证。

(3) 对任意正整数 $n$n ，有：
$\sum _{d\mid n}\frac{\mu \left(d\right)}{d}=\frac{\phi \left(n\right)}{n}$d∣n∑​dμ(d)​=nφ(n)​

证明：
先证：
$n=\sum _{d\mid n}\phi \left(d\right)$n=d∣n∑​φ(d)

令：
$f\left(n\right)=\sum _{d\mid n}\phi \left(d\right)$f(n)=d∣n∑​φ(d)
有：
$f\left(n\right)\ast f\left(m\right)=\sum _{i\mid n}\phi \left(i\right)\ast \sum _{j\mid m}\phi \left(j\right)$f(n)∗f(m)=i∣n∑​φ(i)∗j∣m∑​φ(j)
$=\sum _{i\mid n}\sum _{j\mid m}\phi \left(i\right)\ast \phi \left(j\right)$=i∣n∑​j∣m∑​φ(i)∗φ(j)
因为欧拉函数为积性函数，所以：
$=\sum _{i\mid n}\sum _{j\mid m}\phi (i\ast j)$=i∣n∑​j∣m∑​φ(i∗j)
$=\sum _{d\mid nm}\phi \left(d\right)$=d∣nm∑​φ(d)
$=f(n\ast m)$=f(n∗m)
所以 $f\left(n\right)$f(n) 是积性函数。
根据唯一分解定理：
$n=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k}$n=p1a1​​∗p2a2​​∗...∗pkak​​
所以：
$f\left(n\right)=f(p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k})=f\left(p_1^{a_1}\right)\ast f\left(p_2^{a_2}\right)\ast ...\ast f\left(p_k^{a_k}\right)$f(n)=f(p1a1​​∗p2a2​​∗...∗pkak​​)=f(p1a1​​)∗f(p2a2​​)∗...∗f(pkak​​)
根据定义，有： $f\left(p^a\right)=\phi \left(1\right)+\phi \left(p\right)+\phi \left(p^2\right)+..+\phi \left(p^a\right)$f(pa)=φ(1)+φ(p)+φ(p2)+..+φ(pa)
由欧拉函数性质，当 $n=p^k$n=pk （ $p$p 为素数）， $\phi \left(n\right)=p^k-p^{k-1}$φ(n)=pk−pk−1，有：
$f\left(p^a\right)=1+(p-1)+(p^2-p)+...+(p^a-p^{a-1})=p^a$f(pa)=1+(p−1)+(p2−p)+...+(pa−pa−1)=pa
所以：
$f\left(n\right)=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k}=n$f(n)=p1a1​​∗p2a2​​∗...∗pkak​​=n
所以 $n=\sum _{d\mid n}\phi \left(d\right)$n=d∣n∑​φ(d)
知道这个后，就可以证明性质 $\left(3\right)$(3) 了。
令 $F\left(n\right)=n,f\left(n\right)=\phi \left(n\right)$F(n)=n,f(n)=φ(n)，
所以， $F\left(n\right)=\sum _{d\mid n}f\left(d\right)$F(n)=d∣n∑​f(d)
很明显符合莫比乌斯反演的约数形式，
反演得： $f\left(n\right)=\sum _{d\mid n}\mu \left(d\right)F\left(\frac{n}{d}\right)=\sum _{d\mid n}\mu \left(d\right)\ast \frac{n}{d}$f(n)=d∣n∑​μ(d)F(dn​)=d∣n∑​μ(d)∗dn​
所以： $f\left(n\right)=n\ast \sum _{d\mid n}\frac{\mu \left(d\right)}{d}$f(n)=n∗d∣n∑​dμ(d)​
即： $\sum _{d\mid n}\frac{\mu \left(d\right)}{d}=\frac{\phi \left(n\right)}{n}$d∣n∑​dμ(d)​=nφ(n)​
证毕。

参考博客1
参考博客2

3.线性筛法（基于欧拉筛）

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>prime;
int mob[N];
bool vis[N];
void mobius()
{
    prime.clear();
    memset(vis,0,sizeof(vis));
    mob[1]=1;//莫比乌斯函数第一类情况
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mob[i]=-1;//素数
        }
        for(int j=0;j<prime.size()&&prime[j]*i<N;j++)
        {
            int tmp=i*prime[j];
            vis[tmp]=1;
            if(i%prime[j]==0)
            {
                mob[tmp]=0;//其他情况，因为prime[j]是i的因子，所以k的因子中含有的prime[j]的个数不是1
                break;
            }
            else
               mob[tmp]=-mob[i];//积性函数的性质
        }
    }
}
int main()
{
    mobius();
    for(int i=1;i<=10;i++)
        cout<<mob[i]<<endl;
    return 0;
}

二.莫比乌斯反演：

  当一个函数 $F\left(n\right)$F(n) 很好求时，而其可以写成其 约数 或 倍数 $d$d 的函数 $f\left(d\right)$f(d)， $f\left(d\right)$f(d) 很不好求时，我们可以通过莫比乌斯反演利用 $F\left(n\right)$F(n) 反推 $f\left(d\right)$f(d)，从而快速求解 $f\left(d\right)$f(d)。

$F\left(n\right)$F(n) 和 $f\left(n\right)$f(n) 是定义在非负整数集合上的两个函数。注意 $n$n 和 $d$d 不要弄混。

1.约数形式：

$F\left(n\right)=\sum _{d\mid n}f\left(d\right)⟹f\left(n\right)=\sum _{d\mid n}\mu \left(d\right)\ast F\left(\frac{n}{d}\right)$F(n)=d∣n∑​f(d)⟹f(n)=d∣n∑​μ(d)∗F(dn​)

证明：

${\sum }_{d\mid n}\mu \left(d\right)\ast F\left(\frac{n}{d}\right)={\sum }_{d\mid n}\mu \left(d\right)\ast {\sum }_{k\mid \frac{n}{d}}f\left(k\right)$∑d∣n​μ(d)∗F(dn​)=∑d∣n​μ(d)∗∑k∣dn​​f(k)

$={\sum }_{k\mid n}f\left(k\right){\sum }_{d\mid \frac{n}{k}}\mu \left(d\right)$=∑k∣n​f(k)∑d∣kn​​μ(d) $=f\left(n\right)$=f(n)

$\left(k和d是等价的，原来是一个\mu \right(d\left)对应多个f\right(k),现在是一个f(k\left)对应多个\mu \right(d\left)\right)$(k和d是等价的，原来是一个μ(d)对应多个f(k),现在是一个f(k)对应多个μ(d))

对于 ${\sum }_{d\mid \frac{n}{k}}\mu \left(d\right)$∑d∣kn​​μ(d) ，由莫比乌斯函数的性质，当且仅 $\frac{n}{k}=1$kn​=1 时，其值等于1，否则等于0。

2.倍数形式：

$F\left(n\right)=\sum _{n\mid d}f\left(d\right)⟹f\left(n\right)=\sum _{n\mid d}\mu \left(\frac{d}{n}\right)F\left(d\right)$F(n)=n∣d∑​f(d)⟹f(n)=n∣d∑​μ(nd​)F(d)

证明（同理）：

令 $k=\frac{d}{n}$k=nd​,

${\sum }_{n\mid d}\mu \left(\frac{d}{n}\right)F\left(d\right)$∑n∣d​μ(nd​)F(d)

$={\sum }_{k=1}^{+\infty }\mu \left(k\right)F(n\ast k)$=∑k=1+∞​μ(k)F(n∗k)

$={\sum }_{k=1}^{+\infty }\mu \left(k\right){\sum }_{nk\mid t}f\left(t\right)$=∑k=1+∞​μ(k)∑nk∣t​f(t)

$={\sum }_{n\mid t}f\left(t\right){\sum }_{k\mid \frac{t}{n}}\mu \left(k\right)=f\left(n\right)$=∑n∣t​f(t)∑k∣nt​​μ(k)=f(n)

三.常见应用：

1. $gcd(i,j)$gcd(i,j) 相关问题：

一般先将其转化为求 ${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==1]$∑i=1n​∑j=1m​[gcd(i,j)==1] ，然后利用数论分块解决。

求解 ${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==1]$∑i=1n​∑j=1m​[gcd(i,j)==1] 的过程：

令 $f\left(d\right)={\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==d],num=min(n,m)$f(d)=∑i=1n​∑j=1m​[gcd(i,j)==d],num=min(n,m)

令 $F\left(d\right)=f\left(d\right)+f\left(2d\right)+f\left(3d\right)+...+f\left(kd\right)={\sum }_{d\mid n}^{num}f\left(n\right)$F(d)=f(d)+f(2d)+f(3d)+...+f(kd)=∑d∣nnum​f(n)

即 $F\left(d\right)$F(d) 表示 $gcd(i,j)$gcd(i,j) 为 $d$d 的倍数的二元组的个数，显然 $F\left(d\right)=\lfloor \frac{n}{d}\rfloor \ast \lfloor \frac{m}{d}\rfloor$F(d)=⌊dn​⌋∗⌊dm​⌋，容易求得。这样就可以通过 $F\left(d\right)$F(d) 来求 $f\left(d\right)$f(d)了。

由反演公式，得：

$f\left(d\right)={\sum }_{d\mid n}^{num}\mu \left(\frac{n}{d}\right)F\left(n\right)={\sum }_{d\mid n}^{num}\mu \left(\frac{n}{d}\right)\ast \lfloor \frac{n}{n}\rfloor \ast \lfloor \frac{m}{n}\rfloor$f(d)=∑d∣nnum​μ(dn​)F(n)=∑d∣nnum​μ(dn​)∗⌊nn​⌋∗⌊nm​⌋

(向下取整括号中，上面的 $n,m$n,m 是范围，下面的 $n$n 是变量，注意区分)

当 $d=1$d=1时，有：（记住）

$f\left(1\right)={\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==1]={\sum }_{i=1}^{min(n,m)}\mu \left(i\right)\ast \lfloor \frac{n}{i}\rfloor \ast \lfloor \frac{m}{i}\rfloor$f(1)=∑i=1n​∑j=1m​[gcd(i,j)==1]=∑i=1min(n,m)​μ(i)∗⌊in​⌋∗⌊im​⌋

先预处理出莫比乌斯函数的前缀和，然后用数论分块处理。

各种类型分析及常用方法

<mark>重点【反演解题套路】</mark>：

$\left[gcd\right(i,j)=1]=\sum _{d\mid gcd(i,j)}\mu \left(d\right)=\sum _{d\mid i,d\mid j}\mu \left(d\right)$[gcd(i,j)=1]=d∣gcd(i,j)∑​μ(d)=d∣i,d∣j∑​μ(d)
常见应用过程：

${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)=1]$∑i=1n​∑j=1m​[gcd(i,j)=1]

$={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{d\mid i,d\mid j}\mu \left(d\right)$=∑i=1n​∑j=1m​∑d∣i,d∣j​μ(d)

$={\sum }_{d=1}^{min(n,m)}\mu \left(d\right)\ast \lfloor \frac{n}{d}\rfloor \ast \lfloor \frac{m}{d}\rfloor$=∑d=1min(n,m)​μ(d)∗⌊dn​⌋∗⌊dm​⌋（改变枚举顺序）

证明：
因为莫比乌斯函数性质 $\left(2\right)$(2): $[n=1]=\sum _{d\mid n}\mu \left(d\right)$[n=1]=d∣n∑​μ(d)
问题：

1.求 ${\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)=d](n\le m)$∑i=1n​∑j=1m​[gcd(i,j)=d](n≤m)

$ANS={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{d\mid gcd(i,j)}\mu \left(d\right)={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{d\mid i,d\mid j}\mu \left(d\right)$ANS=∑i=1n​∑j=1m​∑d∣gcd(i,j)​μ(d)=∑i=1n​∑j=1m​∑d∣i,d∣j​μ(d)

$={\sum }_{d=1}^n\left(\mu \right(d)\ast \lfloor \frac{n}{d}\rfloor \ast \lfloor \frac{m}{d}\rfloor )$=∑d=1n​(μ(d)∗⌊dn​⌋∗⌊dm​⌋)（改变枚举顺序，常用的技巧）

四.例题：

1.hdu1695：

先附上一篇详解和思路
主要是利用莫比乌斯反演的性质来构造函数，同时利用了莫比乌斯反演的第二个函数关系。还有思维的转化。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int mu[N];
bool vis[N];
vector<int>prime;
void mobius()
{
    memset(mu,0,sizeof(mu));
    memset(vis,0,sizeof(vis));
    prime.clear();
    mu[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mu[i]=-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<N;j++)
        {
            int tmp=i*prime[j];
            vis[tmp]=1;
            if(i%prime[j]==0)
            {
                mu[tmp]=0;
                break;
            }
            else
                mu[tmp]=-mu[i];
        }
    }
}
int main()
{
    int T,cas=0;
    mobius();
    scanf("%d",&T);
    while(T--)
    {
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("Case %d: ",++cas);
        if(k==0)
        {
            puts("0");
            continue;
        }
        b/=k;
        d/=k;
        long long ans1=0,ans2=0;
        for(int i=1;i<=min(b,d);i++)
            ans1+=(long long)mu[i]*(b/i)*(d/i);
        for(int i=1;i<=min(b,d);i++)
            ans2+=(long long)mu[i]*(min(b,d)/i)*(min(b,d)/i);
        printf("%lld\n",ans1-ans2/2);
    }
    return 0;
}