目录

前置知识

莫比乌斯反演

杜教筛

min_25筛

前置知识

1.乘性函数

对于一个数论函数 $f(n)$

若有两个互质的正整数 $n,m$ ,使得

$$f(nm)=f(n)·f(m)$$

则这个函数为乘性函数

若有任意两个正整数 $n,m$ ,使得

$$f(nm)=f(n)·f(m)$$

则这个函数为完全乘性函数

2.一些常用的乘性函数

$$I(n)=1$$

$$\epsilon(n)=[n=1]$$

$$id^k(n)=n^k$$

$$d(n)=\sum_{i=1}^n[n \space mod \space i=0]$$

$$\sigma_k(n)=\sum_{i=1}^n i^k[n \space mod \space i=0]$$

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

$$\mu(n)$$

3.狄利克雷卷积

对于两个积性函数 $f,g$

我们定义他们的狄利克雷卷积是

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

卷积满足交换律、结合律、分配律。

3.1一些常用的卷积

$$f*\epsilon=f$$

$$I*\mu=\epsilon$$

$$id*\mu=\varphi$$

$$\varphi*I=id$$

$$id*\mu=\varphi$$

莫比乌斯反演

1.定义

若对于 $f,F$ ,有

$$F=f*I$$

$$f=F*\mu$$

2.证明

$$F*\mu=(f*I)*mu$$

$$=f*(I*\mu)$$

$$=f*\epsilon=f$$

3.某些常用套路

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

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

例1 luogu P2257 YY的GCD

$$\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d](n>=m)$$

$$=\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$ $$=\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)$$ $$=\sum_{k=1,k \space is \space prime}^n \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$$

设 $T=kd$ ,则

$$=\sum_{k=1,k \space is \space prime}^n \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(\frac{T}{k})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$$

$$=\sum_{T=1}^n\lfloor \frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k|T,k\space is \space prime}\mu(\frac{T}{k})$$

前半部分数论分块,后半部分可以预处理,达到题目需要的时间复杂度

例2 luogu P3768 简单的数学题

$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij·gcd(i,j)\space mod \space p$$

先不考虑 $p$

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

枚举 $gcd(i,j)$

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

后半部分提出 $d$

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

使用莫比乌斯反演的套路

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

先枚举k

$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}ij$$

$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2(\frac{\lfloor\frac{n}{kd}\rfloor(\lfloor\frac{n}{kd}\rfloor+1)}{2})^2$$

设 $s(n)=\frac{n(n+1)}{2}$

$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2s^2(\lfloor\frac{n}{kd}\rfloor)$$

令 $T=kd$

$$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(\frac{T}{d})T^2s^2(\lfloor\frac{n}{T}\rfloor)$$

先枚举T

$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}\mu(\frac{T}{d})d$$

$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}\mu(\frac{T}{d})id(d)$$

有套路 $\mu*id=\varphi$

$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\varphi(T)$$

于是就变得可做了

而通过另一个套路

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

我们可以获得一种更简单的做法

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

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

$$=\sum_{d=1}^{n}\varphi(d)\sum_{d|i}\sum_{d|j}ij$$

$$=\sum_{d=1}^{n}\varphi(d)d^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij$$

$$=\sum_{d=1}^{n}\varphi(d)d^2s^2(\lfloor\frac{n}{d}\rfloor)$$

所以我们在面对不同的题时,多考虑几种不同的反演方式会使做题速度更快

杜教筛

设两个积性函数 $f,g$

设另一个积性函数 $h=f*g$

记 $s(n)=\sum_{i=1}^n f(i)$

$$\sum_{i=1}^n h(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\lfloor\frac{i}{d}\rfloor)$$

转换枚举方式

$$=\sum_{d=1}^n g(d)·\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$$

$$=\sum_{d=1}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$

提出第一项

$$\sum_{i=1}^n h(i)=g(1)·s(n)+\sum_{d=2}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$

转换一下

$$g(1)·s(n)=\sum_{i=1}^n h(i)-\sum_{d=2}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$

h可以通过前缀和求,而后半段对g求前缀和,s可以进行数论分块

我们处理前 $\sqrt{n}$ 个前缀和可以达到 $o(n^{\frac{3}{4}})$ 的时间复杂度

而经一些巨佬分析可知

处理前 $n^{\frac{2}{3}}$ 个前缀和可以达到更优秀的 $o(n^{\frac{2}{3}})$ 的时间复杂度

例题1

$$s(n)=\sum_{i=1}^{n}\mu(i)$$

考虑套路式 $\mu*I=\epsilon$

$$s(n)=1-\sum_{d=2}^{n}s(\lfloor\frac{n}{d}\rfloor)$$

例2

$$s(n)=\sum_{i=1}^{n}\varphi(i)$$

考虑套路式 $\varphi*I=id$

$$s(n)=\sum_{i=1}^{n}id(i)-\sum_{d=2}^ns(\lfloor\frac{n}{d}\rfloor)$$

$$=\frac{n(n+1)}{2}-\sum_{d=2}^ns(\lfloor\frac{n}{d}\rfloor)$$

例3

$$s(n)=\sum_{i=1}^{n}\varphi(i)i$$

设 $g(n)=i$

此时

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

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

$$=n^2$$

于是

$$s(n)=\sum_{i=1}^ni^2-\sum_{i=2}^ns(\lfloor\frac{n}{d}\rfloor)·i$$

$$s(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{i=2}^ns(\lfloor\frac{n}{d}\rfloor)·i$$

就变得可做了

杜教筛的核心就是抓住套路式,对于一个需要求的 $f$ 的前缀和,我们找出一个合适的 $g$ 便可做了

min_25筛

这个算法针对一类乘性函数的求和问题,这类函数满足它质数及质数次幂的值可以很容易地求出来

通常是一个极其简单的多项式(至少是完全奇性的,并且能够快速求出 $g(n,0)$ ,设其为 $f(x)$ )

$$\sum_{i=1}^{n}F(i)$$

我们先不管这个 $F$ ,我们先来计算

$$\sum_{i=2}^{n}f(i)$$

对这个质数构成的多项式求和

定义 $g(n,j)$ 表示一些数的f(i)的和,这些数是质数或者最小质因子> $P_j$ 的数

我们怎么推这个 $g$ 呢

首先对于 $P_j^2>n$ 的情况,假定 $P_{j-1}^2<=n$

如果它不是质数,则需要最小质因子至少大于 $P_{j-1}$ 也就是 $P_j$

所以这个数至少是 $P_j^2$ ,已经不在范围内了

所以不需要筛掉其他的数了

$$g(n,j)=g(n,j-1)\space\space(P_j^2>n)$$

如果是 $P_j^2<=n$ 的情况呢

我们此时就需要筛掉最小质因子为 $P_j$ 的数

所以我们先拿出一个 $f(P_j)$ ,因为是乘性函数所以成立

剩下的便是 $\frac{n}{P_j}$ ,即需要在小于等于这个数的范围内寻找最小质因子 $>=P_j$ 的,即最小质因子 $>P_{j-1}$ 的,即 $g(\frac{n}{P_j},j-1)$

$$g(n,j)=g(n,j-1)-f(P_j)·g(\frac{n}{P_j},j-1)$$

但是我们就会发现,我们同时也把那些 $<P_j$ 的质数也筛掉了,而这些数乘上 $P_j$ 会出现一些最小质因子 $<P_j$ 的数,而这些数我们不能再筛,所以我们需要还原它们,即 $g(P_j-1,j-1)$

$$g(n,j)=g(n,j-1)-f(P_j)·(g(\frac{n}{P_j},j-1)-g(P_j-1,j-1))\space\space(P_j^2<=n)$$

于是我们就把 $g$ 推出来了

定义

$$S(n,j)=\sum_{i=2}^nF(i),min(p_i)>=P_j$$

表示 $S(n,j)$ 是一些数的 $F(i)$ 的和,其中i的最小质因子大于等于 $P_j$

我们首先考虑质数的贡献

$$g(n,|P|)-g(P_j-1,j-1)$$

这个贡献必须除去最小质因子小于 $P_j$ 的情况,即 $g(P_j-1,j-1)$

然后考虑合数的贡献

我们枚举每个合数的最小质因子的次幂是多少,然后往下递推计算贡献,同时我们也应该考虑合数只由最小质因子构成的情况,即

$$\sum_{i=j}^{P_i^2<=n}\sum_{k=1}^{P_i^{k+1}<=n}(F(P_{i}^k)S(\frac{n}{P_i^k},i+1)+F(P_i^{k+1}))$$

合在一起就是

$$S(n,j)=g(n,|P|)-g(P_j-1,j-1)+\sum_{i=j}^{P_i^2<=n}\sum_{k=1}^{P_i^{k+1}<=n}(F(P_{i}^k)S(\frac{n}{P_i^k},i+1)+F(P_i^{k+1}))$$

最后就会发现

$$\sum_{i=1}^nF(i)=S(n,1)+f(1)$$

得到结果

$g$ 函数可以通过递归或者递推求出, $S$ 函数可以递归求出

理论时间复杂度为 $o(\frac{n^{\frac{3}{4}}}{log\space n})$ ,可以解决 $n$ 的数量级为 $10^{10}$ 左右的求和问题