积性函数线性筛/杜教筛/洲阁筛学习笔记 | Bill Yang's Blog

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

数论函数

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

积性函数

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

完全积性函数

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

常见的积性函数

狄利克雷卷积

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

性质

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

常见的狄利克雷卷积

积性函数的性质

若$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$是一个积性函数。

线性筛的思想

使用最小的$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]$,因此无需继续筛。

1
2
3
4
5
6
7
8
9
10
11
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$的所有质因子,则有:
  • 当$n’\bmod p_1\neq0$,即$a_1=1$时,$n’$与$p_1$互素,而欧拉函数是积性函数,故:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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}$

莫比乌斯函数线性筛

当$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$时,由定义可知:
  • 当$n’\bmod p_1\neq0$,即$a_1=1$时,$n’$与$p_1$互素,而欧拉函数是积性函数,故:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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$的约数个数。

约数个数公式

若$n=\prod_{i=1}^kp_i^{a_i}$,则:

约数个数线性筛

当$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$的指数,由约数个数公式可知:
  • 当$n’\bmod p_1\neq0$,即$a_1=1$时,$n’$与$p_1$互素,而约数个数函数是积性函数,故:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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$的约数个数。

约数和公式

若$n=\prod_{i=1}^kp_i^{a_i}$,则:

约数个数线性筛

当$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$,由约数个数公式可知:
  • 当$n’\bmod p_1\neq0$,即$a_1=1$时,$n’$与$p_1$互素,而约数个数函数是积性函数,故:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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)$的时间内求出特定的积性函数前缀和的方法。
即求出:

要求

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

主过程

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

因此:

即:

因此若$(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$的质因子分为两类,显然有:

第一部分

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

第二部分

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

将$\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)$的值,考虑原式前半部分:

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

考虑转移:

对于一个素数,合法的$j$总数只有$O(\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)$的转移变为:

从小到大枚举$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})$

第三部分

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

将$\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)$。
转移方程为:

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

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

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

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

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

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

参考资料

姥爷们赏瓶冰阔落吧~
0%