莫比乌斯函数

设正整数$N$分解质因数的结果为$N=p_1^{a_1}p_2^{a_2}...p_m^{a_m}$

$\mu(N)= \left\{ \begin{aligned} &0 : \exists ~ i \in [1,m] , a_i>1\\ &1 : m \equiv 0 ~ (mod ~ 2),\forall ~ i \in [1,m] , a_i =1\\ &-1 : m \equiv 1 ~ (mod ~ 2),\forall ~ i \in [1,m] , a_i =1 \end{aligned} \right.$

线性筛法

结论：$\mu(i)$为积性函数(定义证明)

code

void cal_pri(int x)
{
    mu[1]=1;
    for(int i=2;i<=x;i++)
    {
        if(!v[i])
        {
            v[i]=1;
            pri[++top]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=top&&i*pri[j]<=x;j++)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0) 
            {
                mu[i*pri[j]]=0;
                break;
            }
            //mu[pri[j]]=-1
            mu[i*pri[j]]=-mu[i];
        }
    }
}

性质

1. $n \not ={1} \iff \sum_{d \mid n} \mu(d)=0$
2. 结论1拓展：$\sum_{d \mid \gcd(i,j)} \mu(d)=1 \iff \gcd(i,j)=1$

这条性质十分重要，稍后会在例题讲解

莫比乌斯变换(反演)

设$f(n),g(n)$为数论函数

1. 若$f(n)=\sum_{d \mid n}g(d)$，则$g(n)=\sum_{d \mid n} \mu(d) f(\frac{n}{d})$

我们称$f(n)$为$g(n)$的莫比乌斯变换，$g(n)$为$f(n)$的莫比乌斯反演(逆莫比乌斯变换)

2. 若$f(n)=\sum_{n \mid d}g(d)$，则$g(n)=\sum_{n \mid d} \mu(\frac{d}{n}) f(d)$

证明

替换$f(\frac{n}{d})$

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

$n=k$是$\sum_{d \mid \frac{n}{k}}\mu(k)=1$的充要条件

$\sum_{d \mid n} \mu(d) \sum_{k \mid \frac{n}{d}}g(k)=\sum_{k \mid n}g(k) \sum_{d \mid \frac{n}{k}}\mu(d)=g(n)$

现通过两道例题介绍莫反的两种解题思路(最终结果相同)

例题1

[HYSPZ-1001]ZAP

求解

$\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=k]$

Solution

套路：设$f(k)$

$f(k)=\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=k]$

再设$g(k)$

$g(k)=\sum_{k \mid d}f(d)$

感性理解：$g(k)$为$\gcd(i,j)$为$k$的倍数的数量，所以

$g(k)=\lfloor \frac{n}{k} \rfloor \lfloor \frac{m}{k} \rfloor$

于是运用反演公式：

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

于是

$f(k)=\sum_{k \mid d} \mu(\frac{d}{k}) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor$

我们设$\frac{d}{k}=t$

$f(k)=\sum_{t=1}^n\mu(t) \lfloor \frac{n}{kt} \rfloor \lfloor \frac{m}{kt} \rfloor$

除法分块解决上述式子，即可

复杂度$O(T\sqrt{n})$

例题2

[国家集训队]Crash的数字表格

求解

$\sum_{i=1}^n \sum_{j=1}^m lcm(i,j)$

Solution

先拆$lcm$

$\sum_{i=1}^n \sum_{j=1}^m \frac{ij}{\gcd(i,j)}$

枚举$\gcd(i,j)=d$

$\sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i,j)=1]\times ij$

先对$n,m$分别做除法，也就是$n=\lfloor \frac{n}{d} \rfloor,m=\lfloor \frac{m}{d} \rfloor$

先不管左边式子，计算右边式子

$f(n,m)=\sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i,j)=1]\times ij$

根据莫反性质：

$f(n,m)=\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d \mid \gcd(i,j)} \mu(d)\times ij$

$d$提前

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

枚举$i,j$的化简

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

左边式子可以前缀和处理，右边式子

$sum(n,m)=\sum_{i=1}^n \sum_{j=1}^m ij=\frac{n\times (n-1)}{2} \times \frac{m\times (m-1)}{2}$

所以

$f(n,m)=\sum_{d=1}^n \times \mu(d)\times d^2 \times sum(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)$

可以除法分块。

现在回到原式子

$ans=\sum_{d=1}^n d \times f(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)$

也可以除法分块

参考文献

1. OIwiki:莫比乌斯反演，主页
2. 算法竞赛进阶指南:容斥原理和Möbius函数