卷积定义

特指狄利克雷卷积,后面的所有乘号都是狄利克雷卷积运算

运算逻辑是:设f和g是两个数论函数,那么定义两者的狄利克雷卷积为

$(f*g)(n)= \sum_{d|n}f(d)g(\frac{n}{d})$

常见的数论函数

常见的数论函数大部分也都是积性函数($f(ab)=f(a)f(b),gcd(a,b)=1$),比如欧拉函数

$\varphi(n) \ \ \text{欧拉函数}$ $id(n)=n$ $1(n)=1$ $\varepsilon(n)=[n=1]$ $\mu(n)=\begin{cases} 1\ \ \ \ \ \ \ \ \ \ n=1\\ (-1)^k\ \ n=a_1*a_2*\cdots*a_k\ (a_i互不相同,a_i\text{为质数})\\ 0\ \ \ \ \ \ \ \ \ \ x^2|n\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (x为质数) \end{cases}$ $d(n)\ \ \text{约数个数}$ $\sigma(n)\ \ \text{约数和}$

卷积的基本性质

1.满足交换,结合,分配,可以当正常的运算使用
2.在卷积运算中,$\varepsilon(n)$是单位元
3.存在逆元,逆元计算方法为:

$g(n)=\frac{\varepsilon(n)-\sum_{k\zeta=n,k\neq1}f(k)g(\zeta)}f{f(1)}$

卷积运算构成一个交换群,循环群

重要恒等式

$\begin{split} &\ \ \varepsilon=\mu \ * \ 1\\ &id=\varphi\ * \ 1\\ &\ \ d=1\ *\ 1\\ &\ \ \sigma=id\ *\ 1\\ &\ \ \varphi=id\ *\ \mu \end{split}$

证明的话带入一下上面的卷积公式就行,注意此处的乘号全部表示的是狄利克雷卷积

证明 $\varepsilon=\mu \ * \ 1$

$\begin{split} \varepsilon&=(\mu \ *\ 1)(n)\\ &=\sum_{d|n}\mu(d)\cdot1(\frac{n}{d})\\ &=\sum_{d|n}\mu(d)\\ \end{split}$

当n=1时,显然成立,因为$\varepsilon$表示的就是[n=1]
当n>1时,此时根据n的约数分类
若约数能被某个质数的平方整除,显然贡献为0
若这个因数是由多个质数乘积得到的且各质数不重复,那么需要关心质数数量的奇偶性
若是奇数,为-1,反之+1

假设n有k个质数因子,那么根据莫比乌斯函数的定义,可以将式子转化成:

$\sum_{d|n}\mu(d)=\sum_{i=0}^k\left(_i^k\right)(-1)^i=(1-1)^k=0$

最后一步看似有点跳跃,实际上这个是多项式展开的逆过程,原本应该是

$(x-1)^k=\sum_{i=0}^k=(_i^k)x^{k-i}(-1)^i$

然后令x=1就是上面那个式子了,因此第一个恒等式成立

证明$id=\varphi\ * \ 1$

带入得

$\begin{split} id(n)&=\sum_{d|n}\varphi(d)\cdot1(n)\\ &=\sum_{d|n}\varphi(d) \end{split}$

上面这个就是欧拉函数的最重要的式子,然后有关欧拉函数的公式,也一起证明一下

欧拉函数性质证明

1.若$n=p^k$,且p是质数,那么$\varphi(n)=p^k-p^{k-1}$

这个根据欧拉函数的定义可知,因为欧拉函数表示的是小于n且和n互质的数的数量
所以$p,2p,\cdots,p^{k-1}*p$都和n不互质,减一下就是答案了

2.$n=\sum_{d|n}\varphi(d)$

要证明这个,得先证明右边这个函数是一个积性函数

首先先证明,当p是质数时

$\sum_{d|p^k}\varphi(p^k)=\sum_{i=0}^k\varphi(p^i)=p^k$

根据上面的性质1,可以把这个求和式子进行化简

$\sum_{d|p^k}\varphi(p^k)=\sum_{i=0}^k\varphi(p^i)=\varphi(1)+(p-1)+(p^2-p)+\cdots+(p^k-p^{k-1})=p^k$

接下来证明积性函数

设p1,p2为不同质数,那么

$p_1^{k_1}p_2^{k_2}=\sum_{d|p_1^{k_1}}\varphi(p_1^{k_1})\sum_{d|p_2^{k_2}}\varphi(p_2^{k_2})=\sum_{d_1|p_1^{k_1}}\sum_{d2|p_2^{k_2}}\varphi(d_1)\varphi(d_2)$

而欧拉函数在是积性函数,此处gcd(d1,d2)=1,所以

$p_1^{k_1}p_2^{k_2}=\sum_{d_1|p_1^{k_1}}\sum_{d2|p_2^{k_2}}\varphi(d_1)\varphi(d_2)=\sum_{d_1|p_1^{k_1}}\sum_{d2|p_2^{k_2}}\varphi(d_1d_2)$

而d1,d2在遍历中,d1d2显然刚好取遍$p_1^{k_1}p_2^{k_2}$的所有因子,所以上式还能化简为

$p_1^{k_1}p_2^{k_2}=\sum_{d_1|p_1^{k_1}}\sum_{d2|p_2^{k_2}}\varphi(d_1d_2)=\sum_{d|p_1^{k_1}p_2^{k_2}}\varphi(d)$

因此这个函数是一个积性函数

又因为任意n都可以拆分成多个质数相乘,所以等式成立

证明$d=1\ *\ 1$

这个比较直接,带入后得到

$d(n)=\sum_{d|n}1$

显然成立,因此得证

证明$\sigma=id\ *\ 1$

这个也很直接,带入得到

$\sigma(n)=\sum_{d|n}id(d)$

显然成立,因此得证

证明$\varphi=id\ *\ \mu$

两边同时卷1,然后得到

$id=id*\mu *\ 1$

因为

$id*\varepsilon=\sum_{d|n}id(d)\varepsilon(\frac{n}{d})=id$

所以

$id*\varepsilon=id*\mu*1$

然后两边同时再卷上id的逆元,所以得到

$\varepsilon=\mu\ *\ 1$

这个已证明,所以成立

莫比乌斯反演

若数论函数满足:

$g(n)=\sum_{d|n}f(d)$

两边同时卷上$\mu$得到

$\begin{split} g(n)&=\sum_{d|n}f(d)\\ g(n)&=f(n)*1\\ \mu*g(n)&=\mu*f(n)*1\\ \sum_{d|n}\mu(d)g(\frac{n}{d})&=(\mu*1)*f(n)\ (\text{交换律,结合律})\\ \sum_{d|n}\mu(d)g(\frac{n}{d})&=\varepsilon*f(n)\\ \sum_{d|n}\mu(d)g(\frac{n}{d})&=\sum_{d|n}\varepsilon(d)f(\frac{n}{d}) \end{split}$

而最后这步,右边这个式子,只有d取1这一项不为0,所以等于f(n)

因此

$g=1*f\iff f=\mu*g$

狄利克雷前缀和

即以快速求出所有

$b_n=\sum_{d|n}a_d$

其中,a已知,b为前缀和

求法也还是比较好理解的,本质SOS DP(高维前缀和)

其实写的屎山一点的话,就是枚举质数(枚举转移条件),接下来枚举每一个数,要是满足d|n,那么就转移,伪代码可以写成:

for p in primes:
  for i = p..N:
    if i % p == 0:
      F[i] += F[i / p]

按照这个逻辑实现没有问题,但是时间复杂度不好

但是可以注意到内层循环可以优化,优化以后,就是前缀和的代码了

代码:

1
2
3

for(int p:prime)
  for(int d=1;1ll*d*p<=n;d++)
    a[1ll*p*d]+=a[d];

要是求后缀和,反过来就行

代码:

1
2
3

for(int p:prime)
  for(int d=n/p[i];d >=1;d--)
    cnt[d]+=cnt[d*p];

如果还是没法理解,那么先去学SOS dp就行了

线性筛求数论函数的值

这是所有数论题的关键步骤,那么怎么实现呢

线性筛的正确性

每次枚举的是这个数的最小的质数,每个数只会被计算一次或者两次,所以时间上是线性的

并且不会重复,这是枚举规则所带来的结果

线性筛的实现条件

线性筛实现的关键点在于,若一个数能表示为

$n=f(\ p^e\ )\cdot m\ \ (\ m\ mod\ p\neq0\ ,p\text{ 是n的最小质因子})$

要是能通过记录p,e,m,并且$f(p^e)$易于计算,能简单递推出f(n),就存在线性筛法

欧拉函数$\varphi$

最简单是是欧拉函数的线性筛

前面已经证明了

$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}*(p-1)$

所以,当能除尽的时候,需要乘上p-1,否则乘上p就行了

莫比乌斯函数$\mu$

莫比乌斯函数显然只要看这个数的质因数次数就行了

要是能整除,直接设为0,否则取反

约数个数函数d

设

$n=\prod p_i^{a_i}$

那么

$d(n)=\prod(a_i+1)$

首先考虑怎么计算$d(p^e)$

显然等于e+1

那么由于这个函数是性积函数,也就是说当我们计算出d(m)和$d(p^e)$后,可以直接乘积得到答案

所以接下来只需要考虑新加入一个p带来的影响就行了

影响显然是除以cnt[p]+1,再cnt[p]++,再乘以cnt[p]+1

约数和函数$\sigma$

设

$n=\prod p_i^{a_i}$

那么

$\sigma(n)=\prod(1+p_i+\cdots+p_i^{a_i})$

$f(p^e)$可以递推累加,再套个快速幂实现

而约束和也是积性函数,所以也是只要考虑最小的这一位的实现方式就行

所以需要维护的是,p最大幂次,每次快速幂计算一下这一项的和就行

同理,先去除上一次的影响,然后加上这一次的影响,也就是除以上一次的$f(p^{e’})$,再乘上这一次的$f(p^e)$

补充:数论分块

用途是求

$\sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor$

求法也十分易懂,就是计算取这个值的大小有多少个,并且直接算出每次可以取的值

初始时,令l均为1,然后计算右边界

我们要求的是相同值的最大右边界,那么会有:

$\begin{split} &\ \ \ \ \ \lfloor\frac{n}{l}\rfloor\leq\lfloor\frac{n}{r}\rfloor<\lfloor\frac{n}{l}\rfloor+1\\ &\left\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor+1}\right\rfloor+1< l\leq\left\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor \end{split}$

所以得到了右边界r是

$r=\left\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor$

下一次的左边界,显然是r+1,这样就能快速求和了

如果式子为

$\sum_{d=1}^n\left\lfloor\frac{k}{d}\right\rfloor$

算的时候特判就行了,防止算多了

卷积应用示例

例1

求

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

这里会用到

$\varepsilon=\mu*1$

显然里面这个就是$\varepsilon$,所以可以通过卷积转化

所以可以转化原式为:

$\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\mu(d)$

注意到内层的条件是d|gcd(i,j),所以也就是d|i,d|j

那么原式变为

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

尝试交换求和顺序,这里是枚举了i和j,那么如果枚举的是d呢?

每一个d,$\mu(d)$能被算进去的次数为:

$\sum_{d|i,i=1}^n\sum_{d|j,j=1}^m1$

可以发现,当d为定值时,这个也是定值,值为:

$\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$

所以最终式子为:

$\sum_{d=1}^{min(n,m)}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$

线性预处理$\mu$,再用数论分块逐个计算就行了,相当于枚举后面两个的乘积,算一段区间的答案

例2

求

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

方法类似,但是因为后面是gcd,所以得先化成$\varepsilon$的形式

$\sum_{i=1}^n\sum_{j=1}^md\cdot [gcd(\frac{i}{d},\frac{j}{d})==1]\cdot[\ d\ |\ i\ ]\cdot [\ d\ |\ j\ ]$

然后展开gcd那一项

$\sum_{i=1}^n\sum_{j=1}^md\cdot \sum_{k|gcd(\frac{i}{d},\frac{j}{d})}\mu(k)\cdot[\ d\ |\ i\ ]\cdot [\ d\ |\ j\ ]$

显然求和条件和后面的条件一样,所以只保留求和下面那个条件就行了

$\sum_{i=1}^n\sum_{j=1}^md\sum_{k|\frac{i}{d},k|\frac{j}{d}}\mu(k)$

依旧尝试交换求和顺序

$\sum_{d=1}^{min(n,m)}d\sum_{d|i,i=1}^n\sum_{d|j,j=1}^m\mu(k)\ [\ k\ |\ \frac{i}{d}\ ]\ [\ k\ |\ \frac{j}{d}\ ]$

注意观察内层的条件,是直接和$\frac{i}{d}$,$\frac{j}{d}$相关,所以可以进一步化简为:

$\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}\sum_{k|i,k|j}\mu(k)$

这样,内层就变成了和例1中完全一样的式子了,直接套用化简得到

$\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{min(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor)}\mu(k)\left\lfloor\frac{n}{dk}\right\rfloor\left\lfloor\frac{m}{dk}\right\rfloor$

令T=dk,再把式子改成枚举T的形式

$\sum_{T=1}^{min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum_{d|T}d\cdot\mu(\frac{T}{d})$

详细转换步骤:
因为i%d=0,(i/d)%k=0,所以i%(d*k)=0,而i把n范围内的全去了一遍,相当于就是d*k把n范围内全取了一遍

因为T=dk不超过min(n,m),所以上下界就是1和min(n,m)了
然后就是看d和$\mu(k)$的关系了

可以发现d把所有不超范围的k全乘了一次,所以改成枚举T的时候,相当于固定d,选不同的T,也是全取了,所以两者等价

此时发现内层正是

$\varphi=id\ *\ \mu$

所以化简为:

$\sum_{T=1}^{min(n,m)}\varphi(T)\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor$

这样就得到了答案

然后依旧线性筛加数论分块