莫比乌斯反演与数论函数 更新于 2026/7/9 10:52:15 作者

command_block

本博客的第一篇博文哦!纪念。

---- 莫比乌斯反演，本质是利用莫比乌斯函数与其他函数间卷积关系，对函数做一系列简化，从而更高效的解决问题。

---- 数论函数,更广阔的天地,因为$\mu∈\text{数论函数}$

0.写在前面

这里面式子可能比较多,大家多看看证明,尤其是关键证明以及题目推导过程,硬记下的结论越少,越不容易忘记。

(看不清式子可以放大网页)

由于写的时候匆忙,公式可能有错误,请私信或者在下方评论。

每个新东西提出后都会做题或者证明,权当熟悉。

不是一个下午就能看懂的,千万不要直接弃疗

• 给大家简要介绍一下符号的意思。

有时候以$(a,b)$简写$gcd(a,b)$。

$\lfloor a\rfloor$表示下取整,比如$\lfloor 2.33\rfloor=2$

$[???]$表示 : 如果$???$为真,则值为1,否则为0.(就像if里面的东西)

比如 $[(8,6)>2]=0;\ [233=233]=1$

$a|b$表示$a$是$b$的因数,注意,前面是后面的因数。

比如 $[2|4]=1;\ [2|3]=0$

$\sum$称为和式,意思是对……求和。

比如说$\sum\limits_{i}[1\leq i\leq n]i$,表示枚举变量 $i$,对 $[1\leq i\leq n]i$ 求和。

等价于:

int ans=0;
for (int i=1;i<=n;i++)
  ans+=i;

我们常把上界写在上面,下界写在下面,如$\sum\limits_{i=1}^ni=1+2+3+...+n$

有$\sum\limits_{d|6}d=1+2+3+6$ (枚举$6$的因数)

1.狄利克雷卷积与数论函数

——介绍了狄利克雷卷积,数论函数(积性函数)的综合

$\color{blue}\text{定义:}$ 数论函数,就是值域为整数(陪域为复数,但这不重要)的函数。

也就是说下面出现的数没有特殊说明的话,都是整数。

两个数论函数的狄利克雷卷积是一个新函数。

比如$f(n),g(n)$两个函数的狄利克雷卷积写作$\Large{f*g}$ (相当于函数名称)。

什么意思呢?

$\color{blue}\text{定义:}$ $\large{(f*g)(n)=\sum\limits_{d|n}f(d)g(n/d)}$

换句话说就是$\large{(f*g)(n)=\sum\limits_{x*y=n}f(x)g(y)}$

(不过一般不这样写,因为不方便化式子。)

比如说计算$(f*g)(10)$

可得$f(1)g(10)+f(2)g(5)+f(5)g(2)+f(10)g(1)$

(对于某个新东西,能做到的话,理解的最好方式就是手动模拟)

狄利克雷卷积满足以下运算规律(显而易见,不证)：

交换律——$f*g=g*f$;

结合律——$(f*g)*h=f*(g*h)$;

(狄利克雷卷积是一个对称的结构)

下面的推导都基于狄利克雷卷积,有必要好好理解。

介绍几个简单的数论函数,让你有个基本概念。

$I(n)$ 无论$n$是啥,它永远等于1,所以叫做废柴恒等函数

$ϵ(n)$(也作$e(n)$) 当n=1时,函数值为1,否则为0。被称作元函数因为它是卷积的单位元($ϵ*f=f$)。(Important)

$id(n)=n$ 被称作单位函数

附:$id^x(n)=n^x$ 被称作幂函数($id(n)$是$id^x(n)$的特殊情况)

$e(n),I(n),id(n)$是完全积性函数。

$\color{blue}\text{定义:}$完全积性函数: 对于任意的整数a和b有$I(ab)=I(a)I(b)$

附上两个后面会讲的稍微复杂的例子:

$\varphi(n)$ 小于n的整数中,与n互质的数的个数,称作欧拉函数($\varphi(n)$)。

$\mu(n)$ 称作莫比乌斯函数($\mu(n)$)。

$φ(n)$和$\mu(n)$函数是积性函数(我们后面会证明)。

$\color{blue}\text{定义:}$积性函数: 对于一个函数$F$ , 如果$(a,b)=1$时有$F(ab)=F(a)F(b)$,则该函数是积性函数。

积性函数有许多优良性质哦,这些重要的性质我们后面会讲。

很明显,完全积性函数∈积性函数。

下面是一些性质:

• 对于一个积性函数$F$,有$F(1)=1$

$\color{blue}\text{证明:}$ 根据$F(1)=F(1)F(1)$(定义)可得$F(1)=1$。

• 对于函数$F$,积性$→F(x)=F(p_1^{k_1})F(p_2^{k_2})...F(p_m^{k_m})$

这里的$p_1...p_m$是指$x$的$m$个素因子,也就是把$x$分解的结果。

$k_1...k_m$则是$p_1...p_m$对应的次数。

(比方说1800的分解结果就是$2^3*3^2*5^2$)

$\color{blue}\text{证明:}$ 因为$p_1^{k_1},p_2^{k_2},...,p_m^{k_m}$都互质,根据积性易证。

用处:形如$F(prime^k)$的函数值是比较好分析的,我们在利用这个性质来分析一般的情况,后面你们会见到例子。

• 两个积性函数的卷积还是积性函数。

(初学者可以先跳过证明)

设两个积性函数$F_1(x),F_2(x)$。

它们的狄利克雷卷积是$G(n)=\sum\limits_{d|n}F_1(d)F_2(n/d)$

$\color{blue}\text{证明:}$设两数$a,b$互质。

$G(a)G(b)$

$=\sum\limits_{d|a}F_1(d)F_2(a/d)*\sum\limits_{t|b}F_1(t)F_2(b/t)$

$=\sum\limits_{d|a}\sum\limits_{t|b}F_1(d)F_2(a/d)F_1(t)F_2(b/t)$

把$\sum$合并(根据约数集合的合并),由于$a$与$b$互质,所以$t$与$d$互质。

(根据积性可以把$F_1(d)F_1(t)$化为$F_1(dt)$,$F_2$类似)

$=\sum\limits_{dt|ab}F_1(dt)F_2(ab/dt)$

$=G(ab)$,得证.

• 积性函数的逆也是积性函数

(初学者可以先跳过证明)

来介绍一下函数在狄利克雷卷积意义下的逆。

$\color{blue}\text{定义:}$满足$e=g*f$时,$g$和$f$互逆。

(类比同余逆元理解)

附:函数的逆可以通过某种方式构造出来:构造方法(然并卵)

$\color{blue}\text{证明:}$

考虑数学归纳法(跟构造方法有点像)

设$e=G*F$,且$F$是积性函数。

我们要证明对于任意的$(a,b)=1$的$a,b$,都满足$G(ab)=G(a)G(b)$

因为$e=\sum\limits_{d|n}F(d)G(n/d)$

• 1. a或b为1

  当$a=b=1$时,$e(1)=1=F(1)G(1)$

  由于积性,根据上文$F(1)=1$,得$G(1)=1$

  所以当$a$或$b=1$时,结论显然成立。

• 2. ab>1

  我们考虑已证明了所有的$a'<a;\ b'<b$时,结论成立。

  $G(ab)=\sum\limits_{d|ab}F(d)G(ab/d)-\sum\limits_{d|ab,d≠1}F(d)G(ab/d)$

  由$e=G*F$,得$\sum\limits_{d|ab}F(d)G(ab/d)=e(ab)$,由于$ab>1$所以$e(ab)=0$。

  $=-\sum\limits_{d|ab,d≠1}F(d)G(ab/d)$

  $=-\sum\limits_{i|a,j|b,ij≠1}F(ij)G(ab/ij)$

  根据所有的$a'<a;\ b'<b$时,积性成立得

  $=-\sum\limits_{i|a,j|b,ij≠1}F(i)G(j)F(a/i)G(b/j)$

  $=-\sum\limits_{i|a,j|b,ij≠1}F(i)G(a/i)F(j)G(b/j)$

  下面拆分求和号(乘法分配律),这一步有点难。

  $=-\sum\limits_{i|a}F(i)G(a/i)\sum\limits_{j|b,ij≠1}F(j)G(b/j)$

  要求$ij≠1$,即排除$i=j=1$的情况。

  $=F(1)F(1)G(a)G(b)-\sum\limits_{i|a}F(i)G(a/i)\sum\limits_{j|b}F(j)G(b/j)$

  由$e=G*F$,得$\sum\limits_{i|a}F(i)G(a/i)\sum\limits_{j|b}F(j)G(b/j)=e(a)e(b)=0$得

  $=F(1)F(1)G(a)G(b)$

  由于积性,根据上文$F(1)=1$,得

  $=G(a)G(b)$,得证.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

2.莫反公式的推导:

——推导了$\mu$函数,莫比乌斯反演定理

有两个单变量函数 F 与 f 。

设函数 F 与 f 有如下关系：

$F(n)=\sum\limits_{d|n}f(d)$

理解了上述狄利克雷卷积的定义后,不难发现。

$F(n)=\sum\limits_{d|n}(1*f(d))$(废话)

$F=I*f$ (F函数是元函数和f函数的卷积)

现在如果$f$函数易求,那我们可以按照上式算出$F$。

问题在于,如果即$F$函数易求,如何求出$f$?

$F=I*f$,两边同时乘以$I^{-1}$得

$f=I^{-1}*F$

我们只要想办法求出$I^{-1}$就好了。

大佬Möbius把$I^{-1}$命名为$\mu$

问题在于这个函数里面是什么呢?

$\mu$是个积性函数,因为积性函数的逆还是积性函数。

这里有个小技巧,研究一个积性函数,先研究其在质数的幂时的表现。

比如说$\mu(p^k)$(p是质数)。

k=0时,显然有$\mu(1)=1$

k=1时,由于$\sum\limits_{d|p}I(d)\mu(p/d)=e(p)=0$

注意到p为素数,得到$I(p)\mu(1)+I(1)\mu(p)=e(p)=0$

因为$\mu(1)=1$得$1+\mu(p)=0$,即$\large{\mu(p)=-1}$

k>1时,由于$\sum\limits_{d|p^k}I(d)\mu(p^k/d)=e(p^k)=0$

注意到p为素数,得到$I(p^k)\mu(1)+I(p^{k-1})\mu(p)+...+I(1)\mu(p^k)=e(p^k)=0$

所有的$I$都为1,得到$\mu(1)+\mu(p)+\mu(p^2)...+\mu(p^k)=0$

代入$\mu(1)=1,\mu(p)=-1$得到$\mu(p^2)...+\mu(p^k)=0$

考虑上式k=2的情况,得到$\mu(p^2)=0$

考虑上式k=3的情况,得到$mu(p^2)+mu(p^3)=0$也就是$mu(p^3)=0$

……,得到k=任意更大的数时$mu(p^k)=0$

利用数学归纳法,证明了k>1时,$\mu(p^k)=0$。

大家缓口气哦,$\mu$函数的终极定义马上就证明出来了。

由于上文积性函数性质2: $\mu(n=p_1^{k_1}p_2^{k_2}...p_m^{k_m})=\mu(p_1^{k_1})\mu(p_2^{k_2})...\mu(p_m^{k_m})$

因为k>1时,$\mu(p^k)=0$

可以想象到当某一个$k>1$时,$\mu(n)=0$

不然的话所有的k=1。

可以想象到$\mu(n=p_1p_2...p_m)=(-1)^{m}$

mu 函数的$\color{blue}\text{定义}$浮出水面。

现在来介绍莫比乌斯函数是怎么用来反演的。

• 反演公式:

  • 嵌入式莫比乌斯反演：

    由$\mu*I=e$得$\sum\limits_{d|n}\mu(d)=[n=1]$

    注意到$[n|m][n/m=1]=[n=m]$

    则有$[n|m]\sum\limits_{d|(n/m)}\mu(d)=[n=m]$

    初学者可以只掌握这一种。

  • 约数的莫比乌斯反演：

    若：$\large{F(n)=∑\limits_{d|n}f(d)}$

    则：$\large{f(n)=∑\limits_{d|n}μ(d)F(n/d)}$

    又作$f(n)=∑\limits_{d|n}μ(n/d)F(d)$(和上面那个式子等价)

    根据$\mu=I^{-1}$有$f*I=F\rightarrow f=F*\mu$。

    如果你们喜欢和式的话:证明2

  • 倍数的莫比乌斯反演：

    若：$\large{F(n)=∑\limits_{n|d}f(d)}$

    则：$\large{f(n)=∑\limits_{n|d}μ(d/n)F(d)}$

    （这个比较特殊,并不是狄利克雷卷积的形式）

    又作$F(n)=\sum\limits_{k}^∞f(kn)$与$f(n)=\sum\limits_{k}^∞\mu(k)F(kn)$

    $\color{blue}\text{证明:}$

    $∑\limits_{n|d}μ(n/d)F(d)$

    将$F(n)$的定义代入。

    $=∑\limits_{n|d}μ(n/d)\sum\limits_{d|t}f(t)$

    $=∑\limits_{k}^{∞}μ(k)\sum\limits_{nk|t}f(t)$

    第一个求和号对k没有限制,我们交换求和号,考虑枚举t,看有什么对应的k:

    $=∑\limits_{t}f(t)\sum\limits_{nk|t}\mu(k)=∑\limits_{t}f(t)\sum\limits_{k|(t/n),n|t}\mu(k)$

    根据嵌入式反演能得到$\sum\limits_{k|(t/n),n|t}\mu(k)=[t=n]$

    $=∑\limits_{t}f(t)[t=n] =f(n)$,证毕。

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

3.知识储备:

• 分解质因数求法,单个mu(n)

直接按照定义,分解因数暴力求。

代码被和谐
//Time:O(sqrt(n))

• 线性筛法,mu(1~n) (正宗)

利用$\mu$函数的积性性质。

想深入学习线性筛法的看这里。

#include<iostream>
#include<cstring>
#define MaxNum 10000100
using namespace std;
bool e[MaxNum];
int p[MaxNum],tn,mu[MaxNum],n;
void Mobius()
{
  e[1]=1;mu[1]=1;
  for (int i=2;i<=n;i++){
	if (!e[i]){p[++tn]=i;mu[i]=-1;}
	for (int j=1;j<=tn;j++){
	  if (p[j]*i>n)break;
	  mu[p[j]*i]=i%p[j]==0 ? 0 : -mu[i];
	  e[p[j]*i]=1;
	  if (i%p[j]==0)break;
	}
  }
}
int main()
{
  cin>>n; 
  Mobius();
  for(int i=1;i<=n;++i)
   printf("%d: %d\n",i,mu[i]);
  return 0;
}//Time:O(n)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

4.第一道题:整除分块

(除了特殊说明,除法均为整除)

讲了那么多,那么问题来了:我们问什么要学莫比乌斯反演?这有什么用呢?

来看一道题目。

让你求$\large{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[gcd(i,j)=1]}$，也就是互质数对数。($m\leq n$)

大力两重循环+欧几里得$O(n^2logn)$?

悄悄告诉你,正解$O(\sqrt{n})$!

$ANS=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[(i,j)=1]$。

用嵌入式反演替换 : $[(i,j)=1]=\sum\limits_{d|(i,j)}\mu(d)$

• $\color{blue}\text{技巧:}$数对$(i,j)$满足$[d|gcd(i,j)]$的充要条件是$d|i$且$d|j$。

  即$[d|(i,j)]=[d|i][d|j]$, 人话就是 : 即是$i$的约数又是$j$的约数的数是$i,j$的公约数。

则有$[(i,j)=1]=\sum\limits_{d|i,d|j}\mu(d)$,这比较重要。

$ANS=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m\sum\limits_{d|i,d|j}\mu(d)$

$\color{blue}\text{技巧:}$ 我们考虑交换求和顺序,分别查看每个变量的限制。

$d$最先枚举,考虑其范围,显然在$[1,n]$以内。

$i$必须要满足$d|i$,且在$[1,n]$以内。

$j$必须要满足$d|j$,且在$[1,n]$以内。

$ANS=\sum\limits_{d=1}^n\mu(d)\sum\limits_{d|i}^{n}\sum\limits_{d|j}^m1$

观察后面的$\sum\limits_{d|i}^{n}\sum\limits_{d|j}^m1=(\sum\limits_{d|i}^{n}1)(\sum\limits_{d|j}^m1)$

而$\sum\limits_{d|i}^{n}1$相当于$n$以内$d$的倍数的个数,显然为$\lfloor n/d\rfloor$

就得到$ANS=\sum\limits_{d=1}^n\mu(d)\lfloor n/d\rfloor\lfloor m/d\rfloor$

这样子就可以$O(n)$计算了。

$\color{blue}\text{技巧:}$怎么做到$O(\sqrt{n})$呢?需要一个叫做整除分块的技巧。

整除分块入门小记

好的,下面我们默认你会整除分块了。

回顾上面的问题,我们已经变形到了$ANS=∑\limits_{d=1}^{min(n,m)}μ(d)\lfloor n/d\rfloor \lfloor m/d\rfloor$

看到和式后面的$\lfloor n/d\rfloor \lfloor m/d\rfloor$,是可以整除分块的。

问题是还乘了个$\mu(d)$,根据套路弄个前缀和搞定。

(如果这句听不懂,把入门小记再看一遍)

即$\mu([l,r])$的和乘上$\lfloor n/d\rfloor \lfloor m/d\rfloor$。

Code:

#include<iostream>
#define MaxNum 100100
using namespace std;
int p[MaxNum/8],tn,mu[MaxNum],n,m;
bool e[MaxNum];
long long calc(int n,int m)
{
  long long ans=0;
  for (int l=1,r=0;l<=min(n,m);l=r+1){
    r=min(n/(n/l),m/(m/l));// 分段
    ans+=1ll*(mu[r]-mu[l-1])*(n/l)*(m/l);
  }return ans; 
}
int main()
{
    e[1]=1;mu[1]=1;
    for (int i=2;i<=MaxNum;i++){
      if (!e[i]){p[++tn]=i;mu[i]=-1;}
      for (int j=1;j<=tn;j++){
      	if (p[j]*i>MaxNum)break;
      	mu[p[j]*i]=i%p[j]==0 ? 0 : -mu[i];
      	e[p[j]*i]=1;
      	if (i%p[j]==0)break;
      }
    }for (int i=2;i<=MaxNum;i++)mu[i]+=mu[i-1];
    //筛法弄出mu前缀和,参看前文
    cin>>n>>m;
    cout<<calc(n,m)<<endl;
    return 0;
}

后面你会看到,莫比乌斯反演不分块复杂度就是一堆垃圾。

分块是肯定要分块的,这辈子都要分块的

恭喜你,已经在莫比乌斯反演的路上迈出了第一步!

附送可以利用上述代码AC的练手题Link1+Link2

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

5.技巧进阶:莫反常用结论以及练习

莫比乌斯反演是极具技巧性的。

主要的思维难度就建立在反演和分块两部分。

看题吧。

第一题P2568 GCD

求$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=prime]$

在上一题中,我们解决了求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^n[(i,j)=1]$的问题,而且我们已经能够做到$O(\sqrt{n})$求解了。

我们尝试求$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=d]$

• 注意到,$[(i,j)=d]$蕴含$d|i$且$d|j$.

$=\sum\limits_{d|i}^n\sum\limits_{d|j}^n[(i,j)=d]$

• $\color{blue}\text{技巧:}$ 既然$i,j$都是$d$的倍数,我们不妨把$i,j$都除以$d$

  此时,后面原有的$i$需要还原成$id$,原有的$j$要还原成$jd$

$=\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{n/d}[(id,jd)=d]$

• $[(id,jd)=d]=[d(i,j)=d]=[(i,j)=1]$

$=\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{n/d}[(i,j)=1]$,又回到了我们熟悉的问题!

求解的复杂度是$O(\sqrt{n/d})$

对于每个素数求解的复杂度是$O\Big(\sum\limits_{p\in Prime}^{n}{\sqrt{n/p}}\Big)$

$=\sqrt{n}\sum\limits_{p\in Prime}^{n}{\sqrt{1/p}}$

将素数视为平均分布,可估计额$\frac{1}{\log n}\sum\limits_{p=1}^{n}\sqrt{1/p}$

接下来需要一点微积分知识 : $\sum\limits_{p=1}^{n}\sqrt{1/p}=\sqrt{n}$

总的复杂度就是$O(n/\log n)$

对于不会计算复杂度的同学,可以暴力统计一下式子的值,看看能不能过就好了。

Code:

#include<iostream>
#include<cstdio>
#define MaxNum 10000010
using namespace std;
long long p[MaxNum/10],tn,mu[MaxNum+50],anss,ttn,n,aaa;
bool e[MaxNum+50];
void getmu()
{
  e[1]=1;mu[1]=1;
  for (long long i=2;i<=MaxNum;i++){
    if (!e[i])mu[p[++tn]=i]=-1;
  	for (int j=1;j<=tn&&i*p[j]<MaxNum;j++){
	  e[i*p[j]]=1;
  	  mu[i*p[j]]=i%p[j]? -mu[i] : 0;
  	  if (!i%p[j])break;
  	}
  }
} 
//sum(1,N/n)sum(1,N/n)[gcd(i,j)==1]
long long gg(int n){
  long long ans=0;
  for (int l=1,r=0;l<=n;l=r+1){
    r=n/(n/l);			// 分段
    ans+=1ll*(mu[r]-mu[l-1])*(n/l)*(n/l);
  }return ans;
}
int main()
{
  getmu();
  for (int i=2;i<=MaxNum;i++)mu[i]+=mu[i-1];
  cin>>n;
  long long ans=0;
  for (int i=2;i<=n;i++)
   if(!e[i])ans+=gg(n/i);
  cout<<ans;
  return 0;
}

P2257 YY的GCD

貌似和上一题相同呢？发现$T<=10000$。

上一题的$O(n/\log n)$还要乘上数据组数,肯定是跑不过去的。

我们将上面的最终式子整理:

$\sum\limits_{p∈Prime}^{n}f(p)=\sum\limits_{p∈Prime}^{n}∑\limits_{d=1}^{m/p}μ(d)\lfloor n/dp\rfloor\lfloor m/dp\rfloor$

$\color{blue}\text{技巧:}$ 现在又有个蛇皮操作叫改变枚举变量

说起$dp$,我就想起……开机……弘扬中华文化。

还是把$dp$换一下吧,就令$dp=k$我们枚举k。容易发现$dp≤min(n,m)$

明显的,$d$和$p$都是k的约数,我们再枚举$p$,得到$d=k/p$。（把枚举k的和式放在最前面）

$\sum\limits_{k=1}^{min(n,m)}∑\limits_{p∈prime,p|k}μ(k/p)\lfloor n/k\rfloor\lfloor m/k\rfloor$

我们发现只有$μ(k/p)$一项和$p$有关,所以我们可以把$μ(k/p)$连着$∑\limits_{p∈prime,p|k}$一起放到最后面。

得到$\sum\limits_{k=1}^{min(n,m)}\lfloor n/k\rfloor\lfloor m/k\rfloor∑\limits_{p∈prime,p|k}μ(k/p)$

前面的$\sum\limits_{k=1}^{min(n,m)}\lfloor n/k\rfloor\lfloor m/k\rfloor$就可以整除分块了。

至于后面的$∑\limits_{p∈prime,p|k}μ(k/p)$还是套路,维护一个有关于$k$的前缀和。

怎么弄出前缀和,就是考验数论口胡基本功的时候啦,这里也介绍一下。

设$g(k)=∑\limits_{p∈prime,p|k}μ(k/p)$

先线筛出$\mu$,然后枚举$p$,对于 $p|k$ 的$k$将$g[k]+=\mu(k/p)$。(贡献模式,好好理解)

这样的话对于一个素数$p$,复杂度为$O(n/p)$

复杂度和埃氏筛相同,为$O(n\log\log n)$

每个询问$O(\sqrt{n})$,总的复杂度$O(t\sqrt{n}+n\log\log n)$

亮出代码:

#include<algorithm>
#include<cstdio>
using namespace std;
int t,n,m,tn,p[1000500],mu[10000500],g[10000500];
bool e[10000500];
void getmu()
{
  e[1]=1;mu[1]=1;
  for (int i=2;i<=10000100;i++){
  	if (!e[i]){
  	  p[++tn]=i;
  	  mu[i]=-1;
	}for (int j=1;j<=tn;j++){
	  if (1ll*i*p[j]>10000100)break;
	  e[i*p[j]]=1;
	  mu[i*p[j]]=i%p[j] ? -mu[i] : 0;
	  if (!i%p[j])break;
	}
  }//线筛出mu 
}
long long calc(int n,int m)
{
  long long ans=0;
  int l=1,r;
  for (;l<=min(n,m);l=r+1){
  	r=min(n/(n/l),m/(m/l));//整除分块 
  	ans+=1ll*(n/l)*(m/l)*(g[r]-g[l-1]);
  }return ans;
}
int main()
{
scanf("%d",&t);
getmu();
for (int i=1;i<=tn;i++)
 for (int j=p[i];j<=10000100;j+=p[i])
  g[j]+=mu[j/p[i]];
for (int i=2;i<=10000100;i++)g[i]+=g[i-1];
//预处理前缀和 
while(t--){
  	
  scanf("%d%d",&n,&m);
  printf("%lld\n",calc(n,m)); 
  	
}return 0;}

$\color{blue}\text{附加题:}$ P5221 Product & My Sol

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

6.探索新知:其他数论函数

想必经过上面的学习，大家对$\mu$已经有了一定的了解，运用反演定理也更熟练了些，那么我们一起向数论函数这个广阔的天地进发吧!

$\color{blue}\text{定义:}$常用数论函数表：

函数名称	符号	定义	积性	卷积
恒等函数 |	$I(n)$ |	永远等于1 |	完全积性函数 |
元函数 |	$ϵ(n)$(也作$e(n)$) |	当n为1时,函数值为1,否则为0 |
单位函数 |	$id(n)$ |	函数值为n |
幂函数 |	$id^x(n)$ |	函数值为$n^x$ |
莫比乌斯函数 |	$\mu(n)$\mu |	$\mu*I=e$ |	积性函数 |	$\mu*I=e$
欧拉函数|	$\varphi(n)$\varphi |	小于等于n的数中,与n互质的数的个数 |		$\varphi*I=id$
约数个数函数 |	$d(n)$(也作$σ_0(n)$) |	n的约数个数 |		$d=I*I$
约数和函数 |	$σ(n)$ |	n的约数和 |		$σ=id*I$
除数函数 |	$σ^k(n)$ |	n的约数k次方和 |		$σ^k=id^k*I$

1) 欧拉函数

$\color{blue}\text{定义:}$欧拉函数,$\varphi(n)$,其值为“小于等于n的数中,与n互质的数的个数”。

这个函数是可以辅助解（理解）很多的数论题的,它的地位差不多和$\mu$一样重要。

而且，$\varphi$和$\mu$之间有某些神秘联系，这一点要等我们先讲完狄利克雷卷积的一些玩法先。

先讲解这个$\varphi$的基本操作:

$\color{blue}\text{性质:}$首先$\varphi$是积性函数。

$\color{blue}\text{证明:}$因为$\varphi(n)=\sum\limits_{i=1}^n[(n,i)=1]$

设$(n,m)=1$,

得$\varphi(n)\varphi(m)=\sum\limits_{i=1}^n[(n,i)=1]\sum\limits_{j=1}^m[(m,j)=1]$

即$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[(m,j)=1\ {\bf and}\ (n,i)=1]$

由于互质,$[(m,j)=1\ {\bf and}\ (n,i)=1]$等价于$[(nm,im+jn)=1]$。

因为$\gcd\Big((im+jn)\bmod n,n\Big)=\gcd(im,n)=1$,且$\gcd\Big((im+jn)\bmod m,m\Big)=\gcd(jn,m)=1$

我们还要证明所有的$(in+jm)\bmod {nm}$恰好组成$[1...nm]$的集合。

首先,这些二元组的大小为$nm$,和目标集合大小相同,我们只需要证明这些元素两两不同即可。

前置芝士 : $ca=cb\pmod p$且$(c,p)=1$,则有$a=b$. (可见同余系基本定理1)

• 采用反证法,假如有$am+bn=cm+dn\pmod {nm}$

  我们将两边对$m$取模得到$bn=dn\pmod {m}$,由引理得$b=d$,同理有$a=c$,矛盾。

那么$(in+jm)\bmod {nm}$的集合与$[1...nm]$的集合一一对应,且贡献模式相同。

于是上式等价于$\sum\limits_{i=1}^{nm}[(nm,i)=1]=\varphi(nm)$

如何求积性函数的前n个值呢?

线性筛!

对于线性筛,我们要解决$\varphi(prime^k)$类的函数值。(下面的$p$均为素数)

$\color{blue}\text{性质:}$ $\varphi(p^k)=(p-1)p^{(k-1)}$

$\color{blue}\text{证明:}$

$\varphi(p)=p-1$，这是很明显的:小于$p$的数都与$p$互质。

很明显$p^k$以内的数与$p^k$互质的充要条件是:它们没有公因数$p$。

那么把所有含有因数$p$的数去掉,剩下$\dfrac{(p-1)*p^k}{p}=(p-1)p^{(k-1)}$个。

在实用中这个定理有另外一个形式:

如果$p|n$,则$\varphi(np)=\varphi(n)*p$

$\color{blue}\text{证明:}$设$n=p^k*m$,那么$\varphi(n)=\varphi(m)*\varphi(p^k)=\varphi(m)*(p-1)p^{(k-1)}$

则$np=p^{(k+1)}*m$,那么$\varphi(np)=\varphi(m)*\varphi(p^{(k+1)})=\varphi(m)*(p-1)p^k$

原命题明显成立。

Code:

bitset<MaxN> e;
int p[MaxN/10],tn;
long long ans,phi[MaxN];
void getphi()
{
  phi[1]=1;
  for (int i=2;i<=n;i++){
    if (!e[i]){
      p[++tn]=i;
      phi[i]=i-1;
    }for (int j=1,t;j<=tn&&(t=i*p[j])<=n;j++){
      e[t]=1;
      phi[t]=phi[i]*(i%p[j]?p[j]-1:p[j]);
      //此处注意
      if (i%p[j]==0)break;
    }
  }
}

• 代码里"此处注意":

  如果$(i,p)=1$,则$\varphi(ip)=\varphi(i)*\varphi(p)=(p-1)\varphi(i)$

  如果$p|i$,根据上文的定理,$\varphi(ip)=\varphi(i)*p$

• 附: 有些时候我们需要求出单个的$\varphi(n)$,如果按照定义大力求,至少得$O(n)$次$\gcd$。

  我们把$n$分解得$p_1^{k_1}*p_2^{k_2}*...*p_m^{k_m}$

  那么$\varphi(n)=\varphi(p_1^{k_1})*\varphi(p_2^{k_2})*...*\varphi(p_m^{k_m})=\dfrac{(p_1-1)p_1^k}{p_1}*\dfrac{(p_2-1)p_2^k}{p_2}*...\dfrac{(p_m-1)p_m^k}{p_m}$

  $=(p_1^kp_2^{k_2}...p_m^{k_m})*\left(\dfrac{p_1-1}{p_1}*\dfrac{p_2-1}{p_2}*...*\dfrac{p_m-1}{p_m}\right)=n\left(\dfrac{p_1-1}{p_1}*\dfrac{p_2-1}{p_2}*...*\dfrac{p_m-1}{p_m}\right)$

  $\color{blue}\text{性质:}$ $\varphi(n=p_1^kp_2^{k_2}...p_m^{k_m})=n\left(\dfrac{p_1-1}{p_1}*\dfrac{p_2-1}{p_2}*...*\dfrac{p_m-1}{p_m}\right)$

  根据上式,把$n$质因数分解即可求出$\varphi(n)$,复杂度$O(\sqrt{n})$

  Code:

int phi(int n)
{
  int ans=n;
  for (int i=2;i*i<=n;i++)
   if (n%i==0){
   	 ans=ans/i*(i-1);
     //根据上文式子计算
   	 while(n%i==0)n/=i;
   }
  if (n>1)ans=ans/n*(n-1);
  //如果分解不尽,那么肯定还剩一个素数
  return ans;
}

我们来看看$\varphi$的经典应用:

题目

相信你能直接想到一个莫比乌斯反演的做法:

• 设$f(n)$是$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=1]$

  考虑枚举gcd那么答案是$\sum\limits_{d=1}^nd\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=d]$

  后面的$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=d]=\sum\limits_{i=1}^{(n/d)}\sum\limits_{j=1}^{(n/d)}[(i,j)=1]=f(n/d)$

  答案化为$\sum\limits_{d=1}^nd*f(n/d)$。

  对$f(n)$反演,……即为$∑\limits_{d=1}^{n}μ(d)(n/d)^2$,用整除分块求一次$f$时间复杂度$O(\sqrt{n})$

  按$\sum\limits_{d=1}^nd*f(n/d)$计算即可$O(n\sqrt{n})$。

  考虑对$f(n/d)$的$n/d$整除分块,即可$O(n)-O(n^{3/4})$(方法参照上文,证明需用积分)。

其实利用$\varphi$可以很方便地解决上述问题,复杂度是$O(n)-O(\sqrt{n})$。

设$f(n)$是$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=1]$

我们知道$\varphi(n)$的定义是:小于等于n的数中,与n互质的数的个数。

我们把$\varphi(1)+\varphi(2)+...+\varphi(n)$加起来,则可以得到每个数与自己更小的数互质的次数和。

即$\sum\limits_{i=1}^n\sum\limits_{j=1}^i[(i,j)=1]=\sum\limits_{i=1}^n\varphi(i)$

现在，每个数只能统计比自己小的互质产生贡献，也就是，只统计了数对$(x,y)$中$x>=y$的部分。

我们考虑$(x,y)$中$x<=y$的部分贡献,显然和上式相同。

（想像一个邻接矩阵）

乘以$2$就好了，但是由于$(1,1)=1$会多算一次,所以答案减1。

$\color{blue}\text{技巧:}$得到$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=1]=2\left(\sum\limits_{i=1}^n\varphi(i)\right)-1$

我们设$S(n)=\sum\limits_{i=1}^n\varphi(i)$(前缀和),上式变为$f(n)=2*s(n)-1$

答案变为$\sum\limits_{d=1}^nd*f(n/d)=\sum\limits_{d=1}^nd*(2*S(n/d)-1)$已经可以做到$O(n)$了，再整除分快一次就可以$O(\sqrt{n})$了。

然后使用线性筛就得到$O(n)-O(\sqrt{n})$的算法了。

Code:

#include<cstdio>
#include<bitset>
#define MaxN 10000500
using namespace std;
int n;
bitset<MaxN> e;
int p[MaxN/10],tn;
long long ans,phi[MaxN];
void getphi()
{
  phi[1]=1;
  for (int i=2;i<=n;i++){
    if (!e[i]){
      p[++tn]=i;
      phi[i]=i-1;
    }for (int j=1,t;j<=tn&&(t=i*p[j])<=n;j++){
      e[t]=1;
      phi[t]=phi[i]*(i%p[j]?p[j]-1:p[j]);
      if (i%p[j]==0)break;
    }
  }
}
int main()
{
  scanf("%d",&n);
  getphi();
  for (int i=1;i<=n;i++)phi[i]+=phi[i-1];
  for (int i=1;i<=n;i++)ans+=(phi[n/i]*2-1)*i;
  printf("%lld",ans);
}

这个解法相对莫比乌斯反演有什么好处呢?

代码短啊!

如果多组询问的话,就可以使用数论分块$O(\sqrt{n})$回答啦。

重申经典结论:$\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=1]=\left(\sum\limits_{i=1}^n\varphi(i)*2\right)-1$

既然欧拉函数这么好用,为啥还要反演呢?

求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m(i,j)$? 欧拉函数就没法直接按照定义做了。

这么说太过于人类智慧了,下面,我们考虑使用狄利克雷卷积来系统分析。

2)一些狄利克雷卷积结论:

• $id=I*\varphi$

即$\sum\limits_{d|n}\varphi(d)=n$

这个东西是比较重要的,相应地,证明也很长。

$\color{blue}\text{证明:}$设$id*\varphi=F$

我们知道$F$是个积性函数,那么我们只要证明所有的$F(prime^k)=prime^k$成立。

然后根据积性和唯一分解定理,把结论扩展到全体正整数。

$\sum\limits_{d|p^k}\varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+...+\varphi(p^k)$

根据$\varphi(p^k)=(p-1)p^{(k-1)}$,$\varphi(1)=1$

$=1+(p-1)+(p-1)p+(p-1)p^2...+(p-1)p^{(k-1)}$

$=1+(p-1)(1+p+p^2+...p^{(k-1)})$

$=1+(p-1)\dfrac{p^k-1}{p-1}=p^k$

证毕。

根据$I^{-1}=\mu$,可得$id=I*\varphi$等价于$\mu*id=\varphi$

即$\sum\limits_{d|n}\mu(d)(n/d)=\varphi(n)$

这个结论极其有用,比如说我们求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m(i,j)$

利用莫比乌斯反演,变形为$\sum\limits_{d=1}^nd*∑\limits_{t=1}^{n/d}μ(t)\lfloor n/dt\rfloor\lfloor m/dt\rfloor$

设$p=dt$,上式即为

$=\sum\limits_{d=1}^nd*∑\limits_{d|p}^{n}μ(p/d)\lfloor n/p\rfloor\lfloor m/p\rfloor$

可以交换求和号,得到

$=∑\limits_{p=1}^{n}\sum\limits_{d|p}d*μ(p/d)\lfloor n/p\rfloor\lfloor m/p\rfloor$

发现中间的$\sum\limits_{d|p}d*μ(p/d)$就是$\mu*id$所以等于$\varphi(p)$

$=∑\limits_{p=1}^{n}\varphi(p)\lfloor n/p\rfloor\lfloor m/p\rfloor$

(这个式子是可以整除分块的)

这样就可以解决上文留下的问题了。

3)除数函数相关

• $d=I*I$ ;

$\color{blue}\text{证明:}$ $d(n)=\sum\limits_{d|n}1=\sum\limits_{d|n}I(d)I(n/d)=(I*I)(n)$

• $σ=id*I$

$\color{blue}\text{证明:}$ $d(n)=\sum\limits_{d|n}d=\sum\limits_{d|n}id(d)I(n/d)=(id*I)(n)$

把$n$分解得到$p_1^{k_1}*p_2^{k_2}*...*p_m^{k_m}$

$d(n)=(k_1+1)(k_2+1)...(k_m+1)$

$\color{blue}\text{证明:}$对于每个素因子可以选0~k个,乘法原理。

$σ(n)=(1+p_1+p_1^2+...+p_1^{k_1})(1+p_2+p_2^2+...+p_2^{k_2})...(1+p_m+p_m^2+...+p_m^{k_m})$

$=(\dfrac{p_1^{(k_1+1)}-1}{p_1-1})(\dfrac{p_2^{(k_2+1)}-1}{p_2-1})...(\dfrac{p_m^{(k_m+1)}-1}{p_m-1})$

$\color{blue}\text{证明:}$对于每个素因子可以选0~k个,拆完括号后刚好得到所有约数。

另外:$\sum\limits_{i=1}^nd(n)=\sum\limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor$

$\color{blue}\text{证明:}$考虑$i$在1~n中被作为约数的次数,得$\left\lfloor\dfrac{n}{i}\right\rfloor$次。

一道题目

4)一些(跳跃性)结论

在做某些毒瘤题的时候有奇效。

• 莫比乌斯函数$\mu(n)$

有$\mu(ij)=\mu(i)\mu(j)[i\perp j]$

这个容易,假如$(i,j)$大于1,那么一定会导致出现平方因子,式子的值为0.

否则按照积性分解即可。

• 除数函数$d(n)$

有$d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y]$

$\color{blue}\text{证明:}$

比较难,只会从右边推到左边。

把$i$分解得到$p_1^{k_1}*p_2^{k_2}*...*p_m^{k_m}$,$j$分解得到$p_1^{k_1'}*p_2^{k_2'}*...*p_m^{k_m'}$

$d(ij)=(k_1+k_1'+1)(k_2+k_2'+1)...(k_m+k_m'+1)$

显然,每个质因子是独立的,我们考虑$i=p^a;j=p^b$的情况。

$\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y]=\sum\limits_{x'=0}^a\sum\limits_{y'=0}^b[x',y'\text{不同时为正}]$

大眼观察可得只有 $x'$取$0...a$,且$y'$取0这$a+1$个,

$y'$取$0...b$,且$x'$取0这$b+1$个,减去重复算的$(0,0)$,正好是$(a+b+1)$,符合要求。

• 欧拉函数$\varphi(n)$

有$\varphi(ij)=\dfrac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}$

$\color{blue}\text{证明:}$

默认$p$指质数。

$\varphi(ij)=ij\prod\limits_{p|ij}\dfrac{p-1}{p}$

考虑到$[p|ij]=[p|i\ or\ p|j]=[p|i]+[p|j]-[p|(i,j)]$

$=ij\left(\dfrac{\prod\limits_{p|i}\dfrac{p-1}{p}\prod\limits_{p|j}\dfrac{p-1}{p}}{\prod\limits_{p|(i,j)}\dfrac{p-1}{p}}\right)$

$=\dfrac{i\prod\limits_{p|i}\dfrac{p-1}{p}j\prod\limits_{p|j}\dfrac{p-1}{p}(i,j)}{(i,j)\prod\limits_{p|(i,j)}\dfrac{p-1}{p}}$

$=\dfrac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}$