数论GPBH，所以开坑
常见的数论函数
莫比乌斯函数$mu$
1.定义：
- $mu (1)=1$
- 若$d$没有平方因子，$mu (d) = (-1)^k$，$k$为$d$的质因数个数
- 否则$mu (d)=0$
2.性质：
- 对于任意正整数$n$，有$sum limits_{d|n}mu (d)=[n=1]$。
- $mu$为积性函数。
- $sum limits _{d|n}frac{mu(d)}{d}=frac{phi(n)}{n}$
欧拉函数$varphi $
1.定义：
- $varphi (n)= sum limits _{i=1}^{n} [gcd(i,n)=1]$
2.性质：
- $sum limits _{d|n} varphi (d)=n$
- $varphi(n) = n * prod (1 - frac{1}{p_i})$
- $a^{varphi(m)} equiv 1 pmod {m}$
- 对于$n=p^k$，有$varphi(n) = (p - 1) * p^{k - 1}$
- 积性函数
约数个数$d()$
1.定义：
- RT
2.性质：积性函数
约数和$sigma ()$
1.定义：
- RT
2.性质：积性函数
元函数$epsilon$
1.定义：
- $epsilon(n)=[n=1]$
2.性质：
- 对于任意积性函数$f$，有$f*epsilon=f$。
- 积性函数
单位函数$I()$
1.定义：
- $I(n)$恒为1。
2.性质：
- 积性函数
恒等函数$id()$
1.定义：
- $id(n)=n$
2.性质：
- 积性函数
狄利克雷卷积
- 定义：对于两个数论函数$f$和$g$，它们的狄利克雷卷积为$(f*g)(n)=sum limits_{d|n} f(d) cdot g(frac{n}{d})$。
- 性质：狄利克雷卷积满足交换律、结合律和分配律。即：$f*g=g*f$ $(f*g)*h=f*(g*h)$ $(f+g)*h=f*h+g*h$
狄利克雷卷积的一些应用：
1.证明莫比乌斯反演：
假设我们已知：$F(n)=sum_{d|n}f(d)$
考虑利用数论函数将它化成卷积的形式：$F=f*I$
两边卷上$mu$，得到：
$F*mu=f*I*mu$
结合律？
$...=f*(I*mu)$
回忆一下$mu$的性质：
$sum limits _{d|n} mu (d)= [n=1]$
也可以写成：
$I* mu = epsilon$
那么有$...=f*epsilon=f$
把它重新写成普遍形式：$f=F*mu ightarrow f(n)=sum_{d|n}mu(d)cdot F(frac{n}{d})$
2.证明$frac{varphi(n)}{n}=sum limits _{d|n}frac{mu(d)}{d}$
还记得$varphi$的性质嘛？
$sum limits _{d|n} varphi (d)=n$
表示成卷积的形式就是$varphi * I = id$
跟上一个证明类似，如果两边都卷上$mu$：
$varphi * I * mu = id * mu$
$varphi * epsilon =id* mu $
$varphi = id * mu ightarrow sum limits _{d|n} mu (d) cdot frac{n}{d}$
两边同时除以$n$即得证。
杜教筛
终于到了这个大坑……
杜教筛解决的是要求在低于线性时间内求积性函数前缀和的问题。
假设我们要求 $S(n)=sum limits _{i=1}^n f(i)$
那么首先构造两个积性函数$g$和$h$，满足$h=f*g$。
显然有：
$sum limits _{i=1}^{n}h(i)=sum limits _{i=1}^{n}sum limits _{d|i}g(d)cdot f(frac{i}{d})\ o =sum limits_{d=1}^{n}g(d)cdotsum limits_{i=1}^{lfloorfrac{n}{d} floor}f({i})$
停一下。这一步可能会看起来比较懵逼，其实就是把原来先枚举每个数再枚举它的因数，变成了枚举因数并考虑$n$的范围内有多少个数包含它。
我们继续：
$sum limits _{i=1}^{n}h(i)=sum limits _{d=1}^{n}g(d)cdot S(lfloorfrac{n}{d} floor)$
拆出第一项：
$sum limits _{i=1}^{n}h(i)=g(1)cdot S(n)+sum limits _{d=2}^{n}g(d)cdot S(lfloorfrac{n}{d} floor)$
$g(1)S(n)=sum limits _{i=1}^{n}h(i)-sum limits _{d=2}^{n}g(d)cdot S(lfloorfrac{n}{d} floor)$
到了这步，如果你能快速求出$h(i)$的前缀和，就可以通过对后面那项进行整除分块来求出$S(n)$。时间复杂度为$O(n^{frac{2}{3} })$。
比如我们要求的$f$是$mu$，那根据$mu*I=epsilon$可以得到：
$S(n)=1-sum limits _{d=2}^{n}S(lfloorfrac{n}{d} floor)$
筛$varphi$也是同理，利用$varphi*I=id$即可。(其实是我懒得写了所以就同理啦QAQ)
(然而代码实现还不是很熟练……先咕了)
To Be Continued...