积性函数线性筛/杜教筛/洲阁筛学习笔记

数论函数

定义域为正整数的函数，值域为复数的函数。

积性函数

规定$f(1)=1$，当$(a,b)=1$时满足$f(ab)=f(a)f(b)$的函数。

完全积性函数

完全积性函数是积性函数。
满足$\forall a,b$，$f(ab)=f(a)f(b)$。

常见的积性函数

$$e(n)=[n=1]\quad\text{（完全积性）}$$ $$id(n)=n\quad\text{（完全积性）}$$ $$id_k(n)=n^k\quad\text{（完全积性）}$$ $$1(n)=1\quad\text{（完全积性）}$$ $$d(n)=\sum_{i\mid n}1$$ $$\sigma(n)=\sum_{i\mid n}i$$ $$\sigma_k(n)=\sum_{i\mid n}i^k$$ $$\mu(n)=\begin{cases}0 & \exists d\gt1,d^2\mid n \\ (-1)^k & n=\prod_{i=1}^kp_i\end{cases}$$ $$\varphi(n)=\sum_{i=1}^n[(i,n)=1]$$

狄利克雷卷积

定义两个数论函数$f,g$的狄利克雷卷积为：

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

性质

交换律：$f*g=g*f$
结合律：$(f*g)*h=f*(g*h)$
分配率：$f*(g+h)=f*g+f*h$
单位元：$f*e=e*f=f$（$e$是单位函数）

常见的狄利克雷卷积

$$d(n)=\sum_{d\mid n}1\quad\Leftrightarrow\quad d=1*1$$ $$\sigma(n)=\sum_{d\mid n}d\quad\Leftrightarrow\quad \sigma=d*1$$ $$\varphi(n)=\sum_{d\mid n}\mu(d)\frac nd\quad\Leftrightarrow\quad\varphi=\mu*id$$ $$e(n)=\sum_{d\mid n}\mu(d)\quad\Leftrightarrow\quad e=\mu*1$$

积性函数的性质

若$f(x),g(x)$均为积性函数，则：

$h(x)=f(x^p)$为积性函数。
$h(x)=f^p(x)$为积性函数。
相乘$h(x)=f(x)g(x)$为积性函数。
狄利克雷卷积$h(x)=\sum\limits_{d\mid x}f(d)g(\frac xd)$为积性函数。

线性筛

线性筛可以在严格线性的时间内求出积性函数$f(1\rightarrow n)$的值。

要求

$f$是一个积性函数。

线性筛的思想

$$n=\prod_{i=1}^kp_i^{a_i}$$

使用最小的$p_1$去筛掉其他的数。

将$n$分为三类考虑。

1. $n$是质数，根据定义得到$f(i)$的值。
2. $\frac n{p_1}\bmod p_1=0$，说明$\frac n{p_1}$与$n$的质因子集相同，考虑其变化。
3. $\frac n{p_1}\bmod p_1\neq0$，说明$\frac n{p_1}$与$p_1$互素，利用积性函数的性质得到$f(n)=f(\frac n{p_1})f(p_1)$。

素数线性筛

保证每个合数被其最小的素数筛掉，因此时间复杂度是线性的。
当满足$i\bmod p[j]=0$时，说明$p[j]$整除$i$，那么$p[j]$必然整除$i\cdot p[j+1]$，因此无需继续筛。

int vst[maxn],Prime[maxn],cnt=0; //prime

void Prime_Sieve(int n) {
	for(int i=2; i<=n; i++) {
		if(!vst[i])Prime[++cnt]=i;
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0)break;
		}
	}
}

欧拉函数

欧拉函数$\varphi(n)$定义为在$n$以内与$n$互质的正整数个数。

欧拉函数的性质

若$n=p^k$，其中$p$是素数，$\varphi(n)=p^k-p^{k-1}$。

证明：
小于$p^k$的正整数有$p^k-1$个，其中和$p^k$不互质的正整数为$\lbrace p,2p,\ldots,(p^{k-1}-1)p\rbrace$，共$p^{k-1}-1$个数，因此$\varphi(n)=p^k-p^{k-1}$。

若$(p,q)=1$，则$\varphi(pq)=\varphi(p)\varphi(q)$。

证明：
根据上述，$\varphi$是积性函数，因此显然。

设$n=\prod_{i=1}^kp_i^{a_i}$，其中$p_i$是素数，$\varphi(n)=n\prod_{i=1}^k(1-\frac 1{p_i})$。

证明：
由上述两式显然。

欧拉函数线性筛

设$p_1$是$n$的最小质因子，$n’=\frac{n}{p_1}$，在线性筛中，$n$通过$n’\times p_1$被筛掉。

• 当$n’\bmod p_1=0$，即$a_1\gt1$时，$n’$含有$n$的所有质因子，则有： $$\begin{aligned} \varphi(n)&=n\prod_{i=1}^k\frac{p_i-1}{p_i} \\ &=p_1\times n'\prod_{i=1}^k\frac{p_i-1}{p_i} \\ &=p_1\times\varphi(n') \end{aligned}$$
• 当$n’\bmod p_1\neq0$，即$a_1=1$时，$n’$与$p_1$互素，而欧拉函数是积性函数，故： $$\begin{aligned} \varphi(n)&=\varphi(p_1)\times\varphi(n') \\ &=(p_1-1)\varphi(n') \end{aligned}$$

const int maxn=1000005;

int vst[maxn],Prime[maxn],cnt=0; //prime
int Phi[maxn]; //phi

void Phi_Table(int n) {
	Phi[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Phi[i]=i-1;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Phi[i*Prime[j]]=Phi[i]*Prime[j];
				break;
			}
			Phi[i*Prime[j]]=Phi[i]*Phi[Prime[j]];
		}
	}
}

莫比乌斯函数

设$n=\prod_{i=1}^kp_i^{a_i}$

$$\mu(n)=\begin{cases}1 & n=1 \\ (-1)^k & \forall i\in[1,k],a_i=1 \\0 & \exists i\in[1,k],a_i>1\end{cases}$$

莫比乌斯函数线性筛

当$n$为素数时，根据定义有$\mu(n)=-1$。

设$p_1$是$n$的最小质因子，$n’=\frac{n}{p_1}$，在线性筛中，$n$通过$n’\times p_1$被筛掉。

• 当$n’\bmod p_1=0$，即$a_1\gt1$时，由定义可知： $$\mu(n)=0$$
• 当$n’\bmod p_1\neq0$，即$a_1=1$时，$n’$与$p_1$互素，而欧拉函数是积性函数，故：

$$\begin{aligned} \mu(n)&=\mu(p_1)\times \mu(n') \\ &=-1\times \mu(n') \end{aligned}$$

const int maxn=1000005;

int vst[maxn],Prime[maxn],cnt=0; //prime
int Mobius[maxn]; //mobius

void Mobius_Table(int n) {
	Mobius[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Mobius[i]=-1;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Mobius[i*Prime[j]]=0;
				break;
			}
			Mobius[i*Prime[j]]=-Mobius[i];
		}
	}
}

约数个数函数

约数个数函数$d(n)$定义为$n$的约数个数。

$$d(n)=\sum_{i\mid n}1$$

约数个数公式

若$n=\prod_{i=1}^kp_i^{a_i}$，则：

$$d(n)=\prod_{i=1}^k(a_i+1)$$

约数个数线性筛

当$n$为素数时，根据定义有$d(n)=2$。

设$p_1$是$n$的最小质因子，$n’=\frac{n}{p_1}$，在线性筛中，$n$通过$n’\times p_1$被筛掉。

• 当$n’\bmod p_1=0$，即$a_1\gt1$时，设$last$为$n’$中$p_1$的指数，由约数个数公式可知： $$d(n)=d(n')\times\frac{last+2}{last+1}$$
• 当$n’\bmod p_1\neq0$，即$a_1=1$时，$n’$与$p_1$互素，而约数个数函数是积性函数，故： $$\begin{aligned} d(n)&=d(p_1)\times d(n') \\ &=2d(n') \end{aligned}$$

在实现时，使用Min_Divnum[i]来记录$n’=i$时的$last$。

const int maxn=1000005;

int vst[maxn],Prime[maxn],cnt=0; //prime
int d[maxn],Min_Divnum[maxn]; //divisors

void Divisors_Number_Table(int n) {
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Min_Divnum[i]=1;
			d[i]=2;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Min_Divnum[i*Prime[j]]=Min_Divnum[i]+1;
				d[i*Prime[j]]=d[i]/(Min_Divnum[i]+1)*(Min_Divnum[i]+2);
				break;
			}
			Min_Divnum[i*Prime[j]]=1;
			d[i*Prime[j]]=d[i]*d[Prime[j]];
		}
	}
}

约数和函数

约数个数函数$\sigma(n)$定义为$n$的约数个数。

$$\sigma(n)=\sum_{i\mid n}i$$

约数和公式

若$n=\prod_{i=1}^kp_i^{a_i}$，则：

$$\begin{aligned} \sigma(n)&=(1+p_1+p_1^2+\cdots+p_1^{a_1})\times(1+p_2+p_2^2+\cdots+p_2^{a_2})\times\cdots\times(1+p_k+p_k^2+\cdots+p_k^{a_k}) \\ &=\prod_{i=1}^k\sum_{j=0}^{a_i}p_i^j \end{aligned}$$

约数个数线性筛

当$n$为素数时，根据定义有$\sigma(n)=n+1$。

设$p_1$是$n$的最小质因子，$n’=\frac{n}{p_1}$，在线性筛中，$n$通过$n’\times p_1$被筛掉。

• 当$n’\bmod p_1=0$，即$a_1\gt1$时，设$last=p_1^{a_1-1}$也就是$n’$中$p_1$为底的最后一个幂，设$sum=\sum\limits_{i=0}^{a_1-1}p_1^i$，由约数个数公式可知： $$\sigma(n)=\sigma(n')\times\frac{sum+last}{sum}$$
• 当$n’\bmod p_1\neq0$，即$a_1=1$时，$n’$与$p_1$互素，而约数个数函数是积性函数，故： $$\begin{aligned} \sigma(n)&=\sigma(p_1)\times \sigma(n') \\ &=(p_1+1)\sigma(n') \end{aligned}$$

在实现时，使用Min_Fac_last[i]和Min_Fac_sum[i]来记录$n’=i$时的$last$和$sum$。

typedef long long LL;

const int maxn=1000005;

int vst[maxn],Prime[maxn],cnt=0; //prime
LL f[maxn],Min_Fac_last[maxn],Min_Fac_sum[maxn]; //divisors

void Divisors_Sum_Table(int n) {
	f[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Min_Fac_last[i]=i;
			f[i]=Min_Fac_sum[i]=i+1;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Min_Fac_last[i*Prime[j]]=Min_Fac_last[i]*Prime[j];
				Min_Fac_sum[i*Prime[j]]=Min_Fac_sum[i]+Min_Fac_last[i*Prime[j]];
				f[i*Prime[j]]=f[i]/Min_Fac_sum[i]*Min_Fac_sum[i*Prime[j]];
				break;
			}
			f[i*Prime[j]]=f[i]*(Prime[j]+1);
			Min_Fac_last[i*Prime[j]]=Prime[j];
			Min_Fac_sum[i*Prime[j]]=Prime[j]+1;
		}
	}
}

杜教筛

杜教筛是一种可以在$O(n^\frac23)$的时间内求出特定的积性函数前缀和的方法。
即求出：

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

要求

能够找到另一个积性函数$g$，使得$(f*g)(x)$的前缀和与$g(x)$的前缀和都很好计算。

主过程

考虑$(f*g)(x)$的前缀和。

$$\begin{aligned} \sum_{i=1}^n\sum_{j\mid i}f(\frac ij)g(j)&=\sum_{j=1}^n\sum_{j\mid i}^nf(\frac ij)g(j) \\ &=\sum_{j=1}^ng(j)\sum_{i=1}^{\lfloor\frac nj\rfloor}f(i) \\ &=\sum_{i=1}^ng(i)S(\lfloor\frac ni\rfloor) \end{aligned}$$

因此：

$$\sum_{i=1}^ng(i)S(\lfloor\frac ni\rfloor)-\sum_{i=2}^ng(i)S(\lfloor\frac ni\rfloor)=\sum_{i=1}^n\sum_{j\mid i}f(\frac ij)g(j)-\sum_{i=2}^ng(i)S(\lfloor\frac ni\rfloor)$$

即：

$$g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S(\lfloor\frac ni\rfloor)$$

因此若$(f*g)(x)$的前缀和与$g(x)$的前缀和都很好计算，那么可以通过递归，在$O(n^\frac34)$的时间内求出$f$的前缀和。
进一步，若能够通过线性筛预处理$f$在$n^\frac23$内的前缀和，时间复杂度降低到$O(n^\frac23)$。

更具体的，这里分别有欧拉函数与莫比乌斯函数杜教筛的推导。

洲阁筛

杜教筛在时间上虽然很快，但因为其限制条件，并不是所有积性函数都可以使用杜教筛。
洲阁筛可以在$O(\frac{n^\frac34}{\ln n})$的时间内求出大多数积性函数的前缀和。

要求

$f$是一个积性函数。
当$p$是质数时，$f(p^c)$是一个关于$p$的低阶多项式。

洲阁筛的思想

利用$\sqrt n$以外只有$1$个素因子的性质，对素因子进行分类。
再利用除法向下取整只有$\sqrt n$个取值的性质，降低时间复杂度。

主过程

将$[1,n]$中所有数按照是否有$\gt\sqrt n$的质因子分为两类，显然有：

$$\sum_{i=1}^nf(i)=\sum_{i=1}^{\sqrt n}f(i)(\sum_{p\gt\sqrt n,p\text{是素数}}^{\lfloor\frac ni\rfloor}f(p))+\sum_{i=1,i\text{无}\gt\sqrt n\text{的质因子}}^nf(i)$$

第一部分

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

这一部分可以直接线性筛解决。

第二部分

对于每个$1\le i\le\sqrt n$，计算

$$\sum_{p\gt\sqrt n,p\text{是素数}}^{\lfloor\frac ni\rfloor}f(p)$$

将$\sqrt n$以内的素数从小到大排列为$p_1,p_2,\ldots,p_m$。
设$g_k(i,j)$表示$[1,j]$中与前$i$个素数互质的数的$k$次幂和。
这里的$k$无特别含义，仅仅用来表示其可以写作低阶多项式形式。
初值为$g(0,j)=\sum_{t=1}^jt^k$，那么我们需要的值即为$g_k(m,j)$（与前面所有素数互质，必然是$\sqrt n$后的素数），若能$O(1)$得到$g_k(m,j)$的值，考虑原式前半部分：

$$\sum_{i=1}^{\sqrt n}f(i)(\sum_{p\gt\sqrt n,p\text{是素数}}^{\lfloor\frac ni\rfloor}f(p))$$

可用$O(\sqrt n)$的时间枚举$i$，然后$O(1)$得到第二部分。

考虑转移：

$$g_k(i,j)=g_k(i-1,j)-p_i^kg_k(i-1,\lfloor\frac j{p_i}\rfloor)$$

对于一个素数，合法的$j$总数只有$O(\sqrt n)$个，因此粗略计算时间复杂度为：

$$O(\frac{\sqrt n}{\ln\sqrt n}\cdot\sqrt n)=O(\frac n{\ln \sqrt n})$$

需要优化。

注意到当$p_{i+1}\gt j$时，$p_{1\cdots i}$已经可以组成所有数，因此此时未被筛掉的仅有$1$，即$g_k(i,j)=1$。
代入下一层递推可以发现：当$p_i\gt\lfloor\frac j{p_i}\rfloor$，即$p_i^2\gt j$时，$g_k(i,j)$的转移变为：

$$g_k(i,j)=g_k(i-1,j)-p_i^k$$

从小到大枚举$i$，一旦发现对于某个$j$有$p_{i_0}^2>j$便可以不再转移，之后若需要用到其在$i_1$时的值，直接用$g_k(i_0,j)-\sum\limits_{i=i_0}^{i_1-1}p_i^k$即可。

用积分可以将时间复杂度近似为$O(\frac{n^\frac34}{\log n})$

第三部分

$$\sum_{i=1,i\text{无}\gt\sqrt n\text{的质因子}}^nf(i)$$

同样考虑递推，为了剪枝从大的质数往小的递推。

将$\sqrt n$以内的素数从小到大排列为$p_1,p_2,\ldots,p_m$。
设$h(i,j)$表示$[1,j]$中只有$p_{i\cdots m}$质因子的数的$f(x)$求和。

那么初值为$h(m+1,j)=1$，要求$h(0,j)$。
转移方程为：

$$h(i,j)=h(i+1,j)+\sum_{c\ge1}f(p_i^c)h(i+1,\lfloor\frac{j}{p_i^c}\rfloor)$$

发现$j$的取值仍只有$O(\sqrt n)$个，因此暴力计算，时间复杂度仍然为

$$O(\frac{\sqrt n}{\ln\sqrt n}\cdot\sqrt n)=O(\frac n{\ln \sqrt n})$$

注意到当$p_i\gt j$时，能用这些质因子组成的数只有$1$。
因此有$h(i,j)=1$。

类似地，当$p_i^2\gt j$时，转移变为：

$$h(i,j)=h(i-1,j)+f(p_i)$$

从大到小枚举$i$，如果对于某个$j$有$p_i^2\gt j$，可以不转移，每次用的时候加入$[p_i,\min(j,\sqrt n)]$的质数的$f(p)$即可。

时间复杂度仍然为$O(\frac{n^\frac34}{\ln n})$。

嘴上AC还是不难的，现在我还没有用洲阁筛写一道题。

参考资料

• 线性筛法 - Menci
• 初等数论.pdf - h10
• [51nod1239]欧拉函数之和 - alan_cty
• 论逗逼的自我修养之寒假颓废记 - jiry_2
• 洲阁筛学习 - __debug
• 洲阁筛学习总结 - Semiwaker