反演

“撕碎的时空下，宇宙终将反演，就如同没有人能够一直站在主峰上。”

莫比乌斯反演

莫比乌斯函数 $\mu(n)$ 是常数函数 $I(n)$ 在狄利克雷卷积意义下的逆元，即满足 $\mu\ast I=\epsilon$ ，展开式是 $[n=1]=\sum_{d\mid n}\mu(d)$ 。

那么，对于 $p$ 是质数，则有 $0=\mu(1)+\mu(p)$ 。

以此类推，得到 $0=\mu(1)+\mu(p)+\mu(p^2)+…+\mu(p^k)$ 对 $k\ge 2$ 恒成立，从而得到 $\mu(1)=1,\mu(p)=-1$ ，且 $\forall k\ge 2,\mu(p^k)=0$ 。

那么，得出莫比乌斯函数的通常式：

$$\mu(n)= \begin{cases} &1,n=1\\ &0,\exists k_i\ge 2\\ &-1,\forall k_i=1 \nonumber \end{cases}$$

其中 $n=\prod p_i^{k_i}$ 。$p_i$ 为 $n$ 的质因数。可以证明 $\mu(n)$ 为积性函数。

前缀因数定理

有性质 $S(n)=\sum_{i\mid n}\mu(i)=[n=1],n>0$ 。

---

证明：

设 $n=p_1^{d_1}p_2^{d_2}\dots p_k^{d_k},k\ge 1$ ，并设 $d=p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k},0\le \beta_i\le d_i$ 。

可以得到 $S(n)=C_{k}^{0}(-1)^0+C_{k}^1(-1)^1+\dots C_{k}^k(-1)^k$ ，通过二项式定理得到：$S(n)=0,n>0,n\ne 1$ 。

$\operatorname{Q.E.D}$

---

也可以得到 $\mu\ast1=\epsilon$ 。

---

使用

对于莫反，我们可以根据前缀因数定理推出另外一个更有用的式子：

$[\gcd(i,j)=1]=\sum\limits_{d\mid \gcd(i,j)}\mu(d)$

上述式子的正确性显然，因为 $\epsilon(\gcd(i,j))=[\gcd(i,j)=1]$ 。

莫比乌斯反演用于解决两个函数 $f,g$ 同时满足：

$g(n)=\sum_{d\mid n}f(d)$ 与 $f(n)=\sum_{d\mid n}\mu(d)g(\frac{n}{d})$ 。

也可以写成狄利克雷卷积的形式：

$f\ast I=g$ 与 $f=g\ast \mu$

而莫反的题就是构造这个 $f$ 和 $g$ 并求出相应解就可以了。

$$\begin{aligned} f(n)&=\sum_{d\mid n}\mu(d)g(\frac{n}{d}) \\&= \sum_{d\mid n}\mu(d)\sum_{i\mid\frac{n}{d}}f(i) \\&= \sum_{i\mid n}f(i)\sum_{d\mid\frac{n}{i}}\mu(d) \end{aligned}\nonumber$$

---

同样，也可以是满足 $F(n)=\sum_{n\mid d}f(d)$ 和 $f(n)=\sum_{n\mid d}\mu(\frac{d}{n})F(d)$ 的两个函数，也可以证明这两个式子是互相推导的。

---

扩展

有 $\varphi\ast 1=id$

且这个式子两侧同时卷 $\mu$ 得到 $\varphi(n)=\sum\limits_{d\mid n}d\times\mu(\frac{n}{d})$ 。

---

莫比乌斯变换

有式子 $f(n)=\sum_{d\mid n}g(d)$ 和 $g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d})$ 。

其中 $f(n),g(n)$ 为数论函数，且 $f(n)$ 称作 $g(n)$ 的莫比乌斯变换，而 $g(n)$ 称作 $f(n)$ 的莫比乌斯逆变换，或者莫比乌斯反演。

而 $g(n)$ 的莫比乌斯变换，就是将数论函数 $g(n)$ 与常数函数 $1$ 进行狄利克雷卷积。

而形式二，就是 $f(n)=\sum_{n\mid d}g(d)$ 与 $g(n)=\sum_{n\mid d}\mu(\frac{d}{n})f(d)$ 的互推。

---

例题

P1829

显然，转 $\operatorname{lcm}$ 为 $\gcd$ 。

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^m\text{lcm}(i,j) &= \sum_{i=1}^n\sum_{j=1}^m\frac{ij}{\gcd(i,j)} \\&= \sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})=1}\frac{ij}{d} \\&= \sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]i\times j \end{aligned}\nonumber$$

我们记录 $\displaystyle S(n,m)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]iCdot j$ ，化简：

$\displaystyle S(n,m)=\sum_{i=1}^n\sum_{d\mid i}^n\sum_{d\mid j}^m\mu(d)\times i\times j$

设 $i=id,j=jd$ ，得到：

$\displaystyle \sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\times j$

前半段是关于 $d$ 的前缀和，后半段是范围内数对之和，记：

$\displaystyle g(n,m)=\sum_{i=1}^n\sum_{j=1}^mi\times j=\frac{n(n+1)}{2}\times\frac{m(m+1)}{2}$

则有：

$\displaystyle S(n,m)=\sum_{d=1}^n\mu(d)d^2g(\lfloor\frac{n}{d}\rfloor,\lfloor{\frac{m}{d}\rfloor})$

至此，数论分块求解 $S(n,m)$ 即可。

而答案就此得出：

$\displaystyle ans=\sum_{d=1}^nd\times S\left(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor\right)$

时间复杂度 $\mathcal O(n+m)$ 。

---

P2252

运用差分的性质，我们可以设 $S[i,j]$ 表示数 $0\le x\le i,0\le y\le j$ 中满足 $\gcd(x,y)=k$ 的个数，则有：

$ans=S[b,d]-S[a-1,d]-S[b,c-1]+S[a-1,c-1]$

但是暴力的算法时间复杂度可以达到 $\mathcal O(cd\log k)$ ，这是完全不允许的。

所以我们选择构造一个 $F$ 和 $f$ 来进行莫反。

然后一波玄学推出：

$F(n)=\sum\limits_{x=1}^a\sum\limits_{y=1}^a[n|(x,y)]$

$f(n)=\sum\limits_{x=1}^a\sum\limits_{y=1}^b[(x,y)=n]$

所以得到有 $F(n)=\sum\limits_{n\mid d}f(d),f(n)=\sum\limits_{n\mid d}\mu(\frac{d}{n})F(d)$

然后稍微推一推，就可以得到一个更加通常的式子 $F(d)=\lfloor\frac{a}{d}\rfloor\lfloor\frac{b}{d}\rfloor$

所以我们对 $f(n)$ 的式子进行稍微变化：

$$\begin{aligned} f(n)&= \sum_{n\mid d}\mu(\frac{d}{n})\lfloor\frac{a}{d}\rfloor\lfloor\frac{b}{d}\rfloor \\&= \sum_{d'}\mu(d')\lfloor\frac{a}{d'n}\rfloor\lfloor\frac{b}{d'n}\rfloor \\&= \sum_{d'}\mu(d')\lfloor\frac{a'}{d'}\rfloor\lfloor\frac{b'}{n'}\rfloor \end{aligned}\nonumber$$

其中 $d’=\frac{d}{n},a’=\frac{a}{n},b’=\frac{b}{n}$ ，所以这里会使用到数论分块。

易知 $1\sim\lfloor\frac{n}{k}\rfloor$ 中 $d$ 的倍数有 $\lfloor\frac{n}{kd}\rfloor$ 个，故原式化为：

$\sum\limits_{d=1}^{\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$

用数论分块求解即可。

时间复杂度 $\mathcal O(N+T\sqrt n)$ ，其中 $N$ 是预处理时间。

AC Code

#include<bits/stdc++.h>
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int MAXN=5e4+1;
int Pri[MAXN],Mu[MAXN],SumM[MAXN],Tot;
bool Is[MAXN];
inline void Sieve(int N)
{
    Is[1]=1,Mu[1]=1;
    for(int i=2;i<=N;++i)
    {
        if(!Is[i]) Pri[++Tot]=i,Mu[i]=-1;
        for(int j=1;j<=Tot&&i*Pri[j]<=N;++j)
        {
            Is[i*Pri[j]]=1;
            if(i%Pri[j]==0)
            {
                Mu[i*Pri[j]]=0;
                break;
            }
            Mu[i*Pri[j]]=-Mu[i];
        }
    }
    for(int i=1;i<=N;++i) SumM[i]=SumM[i-1]+Mu[i];
}
int Test,a,b,c,d,k;
inline int calc(int n,int m)
{
    int res=0;n/=k,m/=k;
    int tot=std::min(n,m);
    for(int i=1,j;i<=tot;i=j+1)
    {
        j=std::min(n/(n/i),m/(m/i));
        res+=(SumM[j]-SumM[i-1])*(n/i)*(m/i);
    }
    return res;
}
int main()
{
    // freopen("mubius.in","r",stdin);
    // freopen("mubius.out","w",stdout);
    read(Test);
    Sieve(MAXN-1);
    while(Test--)
    {
        read(a,b,c,d,k);
        write(calc(b,d)-calc(a-1,d)-calc(b,c-1)+calc(a-1,c-1)),puts("");
    }
}
/*
2
2 5 1 5 1
1 5 1 5 2
*/

代码里有一些常数小优化。

因为 c++ 里的除法会使常数变大，而对于问题中的 $\lfloor\frac{n}{kd}\rfloor$ 的 $k$ 是常数，所以我们可以先预处理 $\lfloor\frac{n}{d}\rfloor$ ，以免每一次计算的时候都要除一遍 $k$ 实测这样会从 $\text{9.13s}$ 优化到 $\text{4.15s}$ 。

---

P2398

题意非常清晰，推推式子：

$$\begin{align} ans\nonumber =&\nonumber\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) \\=&\nonumber\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[\gcd(i,j)=1] \\=&\nonumber\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}\sum_{k\mid\gcd(i,j)}\mu(k) \\=&\nonumber\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}\sum_{k\mid i\wedge k\mid j}\mu(k) \\=&\nonumber\sum_{d=1}^nd\sum_{k=1}^{\frac{n}{k}}\mu(k)\left(\frac{n}{kd}\right)^2 \nonumber\end{align}$$

预处理出 $\mu$ 的前缀和，然后两次数论分块。

---

P4449

与上一题差不多，但多了一个 $k$ 次方，依然选择推式子。（分数向下取整）

$$ans=\sum_{q=1}^{n}q^k\sum_{d=1}^{\frac{n}{q}}\mu(d)\frac{n}{qd}\frac{m}{qd}\nonumber$$

然后得到：

$$ans=\sum_{q=1}^{n}q^k\sum_{q\mid x}^{\frac{n}{q}}\mu(\frac{x}{q})\frac{n}{x}\frac{m}{x}\nonumber$$

交换顺序：

$$ans=\sum_{x=1}^{n}\frac{n}{x}\frac{m}{x}\sum_{d\mid x}\mu(\frac{x}{q})q^k\nonumber$$

即可。

---

SPOJ 5971

双倍经验

首先，显然地：$\displaystyle \sum_{i=1}^n\operatorname{lcm}(i,n)=\sum_{i=1}^n\frac{in}{\gcd(i,n)}$ ，然后我就想不到了。

$$\begin{aligned} f(n)&= \frac{1}{2}\times(\sum_{i=1}^{n-1}\frac{in}{\gcd(i,n)}\times 2)+n \\&= \frac{1}{2}\left(\sum_{i=1}^{n-1}\frac{in}{\gcd(i,n)}+\sum_{i=n-1}^{1}\frac{in}{\gcd(n-i,n)}\right)+n \\&= \frac{1}{2}\sum_{i=1}^{n-1}\frac{n^2}{\gcd(i,n)}+n \\&= \frac{1}{2}\sum_{i=1}^n\frac{n^2}{\gcd(i,n)}+\frac{n}{2} \\&= \frac{1}{2}\sum_{d\mid n}\left(\frac{n^2\times\varphi(\frac{n}{d})}{d}\right)+\frac{n}{2} \end{aligned}\nonumber$$

上述推导用到的有：

• $\gcd(i,n)=\gcd(n-i,n)$
• $\gcd(i,n)=d$ 的个数有 $\displaystyle\varphi(\frac{n}{d})$ 个。

对于上式，我们设一个 $\displaystyle d’=\frac{n}{d}$ ，简化式子：

$\displaystyle f(n)=\frac{1}{2}n\times\left(\sum_{d’\mid n}d’\times\varphi(d’)+1\right)$

设一个 $\displaystyle g(n)=\sum_{d\mid n}d\times\varphi(d)$ ，可以推出 $g(n)$ 是积性函数，则可以使用线性筛，询问 $\mathcal O(1)$ 。

接下来就考虑怎么筛了，直接拆可以拆出：

$\displaystyle g(p_j^{k})=\sum_{w=0}^kp_j^w\times\varphi(p_j^w)$

又因为 $\varphi(p_j^w)=p_j^{w-1}(p_j-1)$ ，则有：

$\displaystyle g(p_j^k)=\sum_{w=0}^kp_j^{2w-1}Cdot(p_j-1)$

$g(p_j^{k+1})=g(p_j^k)+p_j^{2k+1}Cdot(p_j-1)$

令 $i=a\times p_j^w(\gcd(a,p_j)=1)$ ，则有：

$g(i\times p_j)=g(a)Cdot g(p_j^{w+1})$

$g(i)=g(a)Cdot g(p_j^w)$

因此得到线性筛的式子：

$g(iCdot p_j)=g(i)+\left(g(i)-g(\frac{i}{p_j})\right)\times p_j^2$

AC Code

#include<bits/stdc++.h>
const int MAXN=1e6+1;
int Pri[MAXN],Tot;
bool Is[MAXN];
long long g[MAXN];
inline void Sieve(int N)
{
    Is[1]=1,g[1]=1;
    for(int i=2;i<=N;++i)
    {
        if(!Is[i]) Pri[++Tot]=i,g[i]=1ll*i*(i-1)+1;
        for(int j=1;j<=Tot&&i*Pri[j]<=N;++j)
        {
            Is[i*Pri[j]]=1;
            if(i%Pri[j]==0)
            {
                g[i*Pri[j]]=g[i]+(g[i]-g[i/Pri[j]])*Pri[j]*Pri[j];
                break;
            }
            g[i*Pri[j]]=g[i]*g[Pri[j]];
        }
    }
}
int Test,N;
int main()
{
    scanf("%d",&Test);
    Sieve(MAXN-1);
    while(Test--)
    {
        scanf("%d",&N);
        printf("%lld\n",(g[N]+1)*N/2);
    }
}
/*
3
1
2
5
*/

---

欧拉反演

欧拉函数 $\varphi$ 满足 $\varphi\ast I=id$ ，即 $n=\sum_{d\mid n}\varphi(d)$ ，且欧拉函数是积性函数。

所谓欧拉反演，就是在使用的时候把 $n$ 拆成 $\sum_{d|n}\phi(d)$ 。

因为有 $\mu\ast I=\epsilon,\varphi\ast I=id,id\ast \mu=\varphi$ ，所以莫比乌斯和欧拉是可以互相反演的。

例题

P2398

同样可以用欧拉反演推出式子，省略过程（主要是懒得写了），直接给出结果：

$ans=\sum\limits_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor^2$

---

总结

对于这类题而言，只需要记住两个公式和两个思路即可：

1. $\displaystyle\sum_{p\mid d}\varphi(p)=d$
2. $\displaystyle\sum_{p\mid d}\mu(p)=[d=1]$

即，一个数的因数的欧拉函数的和等于它本身，它因数的莫比乌斯函数的和在这个数为 $1$ 时等于 $1$ ，否则等于 $0$ 。

那么，两个思路是什么呢？

代换和提前。

什么是代换？

就比如说：

$$\begin{aligned} \sum_{i}^{n}\sum_{j}^{n}\gcd(i,j) &= \sum_{i}^{n}\sum_{j}^{n}\sum_{d\mid\gcd(i,j)}\varphi(d) \end{aligned}$$

就是所谓的代换。

把类似于 $\gcd$ ，或者 $\operatorname{lcm}$ 这类不太好处理的式子代换成像 $\varphi,\mu$ 这类容易处理的积性函数，就是代换的思想，

那什么又是提前？

继续化简上面的式子：

$$\begin{aligned} \sum_{i}^{n}\sum_{j}^{n}\sum_{d\mid\gcd(i,j)}\varphi(d) &= \sum_{d\mid\gcd(i,j)}\sum_{i}^{n}\sum_{j}^{n}\varphi(d) \\&= \sum_{d}^{n}\varphi(d)\sum_{i}^{\lfloor\frac{n}{d}\rfloor}\sum_{j}^{\lfloor\frac{n}{d}\rfloor} \end{aligned}$$

我们选择将 $\varphi(d)$ 提前，使得后面的项与 $\varphi(d)$ 无关，然后我们会发现，枚举的 $i,j$ 是空的，所以可以直接计算：

$$\begin{aligned} \sum_{d}^{n}\varphi(d)\sum_{i}^{\lfloor\frac{n}{d}\rfloor}\sum_{j}^{\lfloor\frac{n}{d}\rfloor} &= \sum_{d}^{n}\varphi(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{n}{d}\rfloor \\&= \sum_{d}^{n}\varphi(d)\lfloor\frac{n}{d}\rfloor^2 \end{aligned}$$

前半段的 $\displaystyle\sum_{d=1}^{n}\varphi(d)$ 可以线性筛预处理，后半段直接整数分块解决。

---

这是直接利用反演结论做题的思路，而对于我们上述提到的反演公式：$f(n)=\sum_{d\mid n}g(d)$ ，则是对于反演题的另一个思路，是给类似于 $\text{mydcwfy}$ 这种巨佬的。

像我一样，就用这种傻瓜思路吧。