# 铃悬的数学小讲堂——杜教筛 本篇在读者掌握莫比乌斯反演与狄利克雷卷积的前提下，讲述了杜教筛算法，并伴有若干例题；另外还解释了如何利用贝尔级数更方便的使用杜教筛（要求具有一定生成函数知识）。
如果掌握莫比乌斯反演，也建议看一遍上篇博客；因为可能某些符号不太一样。
-2.符号及规定 同上篇。为方便此处再次写出：
[ P ] [P] [ P ] P P P 1 1 1 P P P 0 0 0 P 是一个 0/1 布尔值， [ P ] [P] [ P ] (int)P。a ∣ b a\mid b a ∣ b b b b a a a k k k b = k a b=ka b = ka n ⊥ m n\perp m n ⊥ m n n n m m m 1 ⊥ 1 1\perp1 1 ⊥ 1 数论函数（见下）用小写粗体字母或普通希腊文字母（如 f , g , h , μ , ϵ {\bf f,g,h},\mu,\epsilon f , g , h , μ , ϵ
-1.前备知识 至少要理解莫比乌斯反演篇中的知识（即使不知道证明）qwq。
0.数论分块 对于一个像
F ( n ) = ∑ i = 1 n f ( i ) ⌊ n i ⌋ F(n)=\sum_{i=1}^n f(i)\lfloor\frac ni\rfloor F ( n ) = ∑ i = 1 n f ( i ) ⌊ i n ⌋ 这样的式子，如果我们可以
O ( 1 ) O(1) O ( 1 ) 求出
f ( i ) f(i) f ( i ) 的区间和，那么则可以在
O ( n ) O(\sqrt n) O ( n ) 的复杂度内计算
F ( n ) F(n) F ( n ) 。这依赖于以下引理：
引理 0.1
不同的
⌊ n i ⌋ \lfloor\frac ni\rfloor ⌊ i n ⌋ 只有
O ( n ) O(\sqrt n) O ( n ) 种。
证明实际上很简单：如果
i ≥ n i\geq\sqrt n i ≥ n ，那么
1 ≤ ⌊ n i ⌋ ≤ n 1\leq\lfloor\frac ni\rfloor\leq\sqrt n 1 ≤ ⌊ i n ⌋ ≤ n ，又只取整数值，自然只有
O ( n ) O(\sqrt n) O ( n ) 种取值。否则
i < n i<\sqrt n i < n ，但这样的
i i i 只有
n \sqrt n n 种，自然也只会有
O ( n ) O(\sqrt n) O ( n ) 种取值。
至于如何找出每一种取值，以及确定每个值对应的
i i i 的区间，可以参考以下代码：
CPP int ans = 0 ;
for (int i = 1 , j; i <= n; i = j + 1 ) {
j = n / (n / i);
ans += (n / i) * S (i, j);
}
代码中
S ( a , b ) S(a,b) S ( a , b ) 指
∑ i = a n f ( i ) \sum_{i=a}^n f(i) ∑ i = a n f ( i ) 。这段代码即可求出
∑ i = 1 n f ( i ) ⌊ n i ⌋ \sum_{i=1}^n f(i)\lfloor\frac ni\rfloor ∑ i = 1 n f ( i ) ⌊ i n ⌋ 。
至于代码中的注释，则是因为
⌊ n t ⌋ ≥ ⌊ n i ⌋ ⟺ n t ≥ ⌊ n i ⌋ ⟺ t ≤ n ⌊ n i ⌋ ⟺ t ≤ ⌊ n ⌊ n i ⌋ ⌋ \left\lfloor\frac nt\right\rfloor\geq\left\lfloor\frac ni\right\rfloor\iff \frac nt\geq\left\lfloor\frac ni\right\rfloor\iff t\leq\frac n{\left\lfloor\frac ni\right\rfloor}\iff t\leq\left\lfloor\frac n{\left\lfloor\frac ni\right\rfloor}\right\rfloor ⌊ t n ⌋ ≥ ⌊ i n ⌋ ⟺ t n ≥ ⌊ i n ⌋ ⟺ t ≤ ⌊ i n ⌋ n ⟺ t ≤ ⌊ ⌊ i n ⌋ n ⌋
所以 t 的最大值就是
n/(n/i) 。
如果求和上界是
m m m 而不是
n n n （
m ≤ n m\leq n m ≤ n ），那就吧循环条件写成
i ≤ m i\leq m i ≤ m 并令
j=min(m,n/(n/i)) 即可。
∑ i = 1 n f ( i ) g ( ⌊ n i ⌋ ) \sum_{i=1}^n f(i)g(\lfloor\frac ni\rfloor) ∑ i = 1 n f ( i ) g (⌊ i n ⌋) 也可以用相同求法求。
同样的，如果求
∑ i = 1 min ( n , m ) f ( i ) ⌊ n i ⌋ ⌊ m i ⌋ \sum_{i=1}^{\min(n,m)}f(i)\lfloor\frac ni\rfloor\lfloor\frac mi\rfloor ∑ i = 1 m i n ( n , m ) f ( i ) ⌊ i n ⌋ ⌊ i m ⌋ ，也只需要令
j=min(n/(n/i),m/(m/i))，复杂度仍旧是
O ( max ( n , m ) ) O(\sqrt{\max(n,m)}) O ( max ( n , m ) ) 。
1.杜教筛 如果给定函数
f , g \bf f,g f , g ，令
S ( n ) = ∑ i = 1 n f ( i ) {\bf S}(n)=\sum_{i=1}^n{\bf f}(i) S ( n ) = ∑ i = 1 n f ( i ) ，则有
∑ i = 1 n ( f ∗ g ) ( i ) = ∑ i = 1 n ∑ x y = i f ( x ) g ( y ) = ∑ y = 1 n g ( y ) ∑ x y ≤ n f ( x ) = ∑ y = 1 n g ( y ) S ( ⌊ n y ⌋ ) \sum_{i=1}^n({\bf f*g})(i)=\sum_{i=1}^n\sum_{xy=i}{\bf f}(x){\bf g}(y)=\sum_{y=1}^n{\bf g}(y)\sum_{xy\leq n}{\bf f}(x)=\sum_{y=1}^n{\bf g}(y){\bf S}\left(\left\lfloor\frac ny\right\rfloor\right) ∑ i = 1 n ( f ∗ g ) ( i ) = ∑ i = 1 n ∑ x y = i f ( x ) g ( y ) = ∑ y = 1 n g ( y ) ∑ x y ≤ n f ( x ) = ∑ y = 1 n g ( y ) S ( ⌊ y n ⌋ )
换句话说，
g ( 1 ) S ( n ) = ∑ i = 1 n ( f ∗ g ) ( i ) − ∑ y = 2 n g ( y ) S ( ⌊ n y ⌋ ) {\bf g}(1){\bf S}(n)=\sum_{i=1}^n({\bf f*g})(i)-\sum_{y=2}^n{\bf g}(y){\bf S}\left(\left\lfloor\frac ny\right\rfloor\right) g ( 1 ) S ( n ) = ∑ i = 1 n ( f ∗ g ) ( i ) − ∑ y = 2 n g ( y ) S ( ⌊ y n ⌋ )
这是由上面的等式右侧除了
y = 1 y=1 y = 1 一项之外都移项到左边得到的。
由此我们可以得到一个
S {\bf S} S 的计算方法（假设
( f ∗ g ) ( i ) ({\bf f*g})(i) ( f ∗ g ) ( i ) 的前缀和与
g ( i ) {\bf g}(i) g ( i ) 的区间和都可以
O ( 1 ) O(1) O ( 1 ) 计算，以下计算复杂度时亦作此假设）：
CPP int S (int n) int ans = ???;
for (int i = 2 , j; i <= n; i = j + 1 ) {
j = n / (n / i);
ans -= Sg (i, j) * S (n / i);
}
ans /= g1;
return ans;
}
其中
ans 初值为
∑ i = 1 n ( f ∗ g ) ( i ) \sum_{i=1}^n({\bf f*g})(i) ∑ i = 1 n ( f ∗ g ) ( i ) ，
S g ( i , j ) = ∑ k = i j g ( k ) {\bf Sg}(i,j)=\sum_{k=i}^j{\bf g}(k) Sg ( i , j ) = ∑ k = i j g ( k ) 。
这段代码如何优化复杂度呢？首先估计计算
S ( N ) {\bf S}(N) S ( N ) 的过程中产生了多少递归计算。
以下，我们以
N N N 指最初给出的
n n n ，以
n n n 指递归调用产生的
n n n 。
引理1.1
对于任意正整数
x , y , z x,y,z x , y , z ，有
⌊ ⌊ z x ⌋ y ⌋ = ⌊ z x y ⌋ \left\lfloor\frac{\left\lfloor\frac zx\right\rfloor}y\right\rfloor=\left\lfloor\frac z{xy}\right\rfloor ⌊ y ⌊ x z ⌋ ⌋ = ⌊ x y z ⌋
证明也很简单：假设
z = a x + b , a = c y + d z=ax+b,a=cy+d z = a x + b , a = cy + d ，其中
0 ≤ b < x , 0 ≤ d < y 0\leq b<x,0\leq d<y 0 ≤ b < x , 0 ≤ d < y ，那么显然
⌊ z x ⌋ = a , ⌊ a y ⌋ = c \left\lfloor\frac zx\right\rfloor=a,\left\lfloor\frac ay\right\rfloor=c ⌊ x z ⌋ = a , ⌊ y a ⌋ = c ，于是等号左边就等于
c c c 。同样的，我们有
z = c x y + ( d x + b ) z=cxy+(dx+b) z = c x y + ( d x + b ) ，其中
0 ≤ d x + b ≤ ( y − 1 ) x + ( x − 1 ) = x y − 1 < x y 0\leq dx+b\leq(y-1)x+(x-1)=xy-1<xy 0 ≤ d x + b ≤ ( y − 1 ) x + ( x − 1 ) = x y − 1 < x y ，所以
⌊ z x y ⌋ = c \left\lfloor\frac z{xy}\right\rfloor=c ⌊ x y z ⌋ = c 。所以等号左右相等。
由此可以发现，上面的代码在计算
S ( N ) {\bf S}(N) S ( N ) 时，产生的（直接的或间接的）递归计算中的
n n n 都是某个
⌊ N x ⌋ \left\lfloor\frac Nx\right\rfloor ⌊ x N ⌋ （因为如果这次的
n n n 是
⌊ n x ⌋ \lfloor\frac nx\rfloor ⌊ x n ⌋ ，下次一定是某个
⌊ ⌊ n x ⌋ i ⌋ = ⌊ n x i ⌋ \left\lfloor\frac{\lfloor\frac nx\rfloor}i\right\rfloor=\lfloor\frac n{xi}\rfloor ⌊ i ⌊ x n ⌋ ⌋ = ⌊ x i n ⌋ )，从而根据引理 0.1 只有
O ( N ) O(\sqrt N) O ( N ) 次递归调用（如果
n n n 相等的只计算一次的话），记忆化即可。
如果略去递归调用的复杂度，显然计算一次
S ( n ) {\bf S}(n) S ( n ) 是
O ( n ) O(\sqrt n) O ( n ) 。根据引理 0.1 的证明过程可知递归调用的
n n n 分别为
1 , 2 , … , N , ⌊ N 1 ⌋ , ⌊ N 2 ⌋ , … ⌊ N N ⌋ 1,2,\dots,\sqrt N,\lfloor\frac N1\rfloor,\lfloor\frac N2\rfloor,\dots\lfloor\frac N{\sqrt N}\rfloor 1 , 2 , … , N , ⌊ 1 N ⌋ , ⌊ 2 N ⌋ , … ⌊ N N ⌋ 。于是复杂度为
O ( ∑ i = 1 N i + ∑ i = 1 N ⌊ N i ⌋ ) = O ( ∑ i = 1 N ⌊ N i ⌋ ) = O ( ∫ 1 N N x d x ) = O ( N 3 4 ) O\left(\sum_{i=1}^{\sqrt N}\sqrt i+\sum_{i=1}^{\sqrt N}\sqrt{\left\lfloor\frac Ni\right\rfloor}\right)=O\left(\sum_{i=1}^{\sqrt N}\sqrt{\left\lfloor\frac Ni\right\rfloor}\right)=O\left(\int_1^{\sqrt N}\sqrt{\frac Nx}{\rm d}x\right)=O\left(N^{\frac34}\right) O ( ∑ i = 1 N i + ∑ i = 1 N ⌊ i N ⌋ ) = O ( ∑ i = 1 N ⌊ i N ⌋ ) = O ( ∫ 1 N x N d x ) = O ( N 4 3 )
第一步等号是因为后面的求和项显然比左边的大，所以在大
O O O 符号中左边的可以省略。第二步等号为积分近似。
但是我们不能满足于此。我们发现如果对于较小的
n n n 仍然
O ( n ) O(\sqrt n) O ( n ) 计算
S {\bf S} S 是不明智的，因为大部分情况下我们可以
O ( n ) O(n) O ( n ) 预处理出
S ( 1 ) , S ( 2 ) , … S ( n ) {\bf S}(1),{\bf S}(2),\dots{\bf S}(n) S ( 1 ) , S ( 2 ) , … S ( n ) （利用线性筛一类）。我们如果预处理出
1 … N c ( c > 1 2 ) 1\dots N^c(c>\frac12) 1 … N c ( c > 2 1 ) 的答案，那么需要递归计算的只剩下
⌊ N 1 ⌋ , ⌊ N 2 ⌋ , … ⌊ N N 1 − c ⌋ \lfloor\frac N1\rfloor,\lfloor\frac N2\rfloor,\dots\lfloor\frac N{N^{1-c}}\rfloor ⌊ 1 N ⌋ , ⌊ 2 N ⌋ , … ⌊ N 1 − c N ⌋ ，于是复杂度变成
O ( N c + ∑ i = 1 N 1 − c ⌊ N i ⌋ ) = O ( N c + ∫ 1 N 1 − c N x d x ) = O ( N c + N 1 − 1 2 c ) O\left(N^c+\sum_{i=1}^{N^{1-c}}\sqrt{\left\lfloor\frac Ni\right\rfloor}\right)=O\left(N^c+\int_1^{N^{1-c}}\sqrt{\frac Nx}{\rm d}x\right)=O\left(N^c+N^{1-\frac12 c}\right) O N c + i = 1 ∑ N 1 − c ⌊ i N ⌋ = O ( N c + ∫ 1 N 1 − c x N d x ) = O ( N c + N 1 − 2 1 c ) 取
c = 2 3 c=\frac23 c = 3 2 时复杂度最优，为
O ( N 2 3 ) O(N^{\frac23}) O ( N 3 2 ) 。
对于记忆化：可以使用
map，但会导致复杂度多一个
log \log log 。
更好的做法是，由于递归调用的
n n n 总是某个
⌊ N x ⌋ \lfloor\frac Nx\rfloor ⌊ x N ⌋ ，并且
x > n 1 3 x>n^{\frac13} x > n 3 1 的时候都会直接查预处理的表，所以可以直接记
Ans[x] 表示
⌊ N x ⌋ \lfloor\frac Nx\rfloor ⌊ x N ⌋ 的答案。详细代码例题中会给出。
对于计算
∑ i = 1 n ( f ∗ g ) ( i ) \sum_{i=1}^n({\bf f*g})(i) ∑ i = 1 n ( f ∗ g ) ( i ) ，由于后面还有
O ( n ) O(\sqrt n) O ( n ) 的递归复杂度，所以这个东西只要在
O ( n ) O(\sqrt n) O ( n ) 时间算完就不影响杜教筛复杂度；或者因为
n n n 都是
⌊ N x ⌋ \lfloor\frac Nx\rfloor ⌊ x N ⌋ ，所以这个也可以套一层杜教筛。
∑ i = 1 n g ( i ) \sum_{i=1}^n{\bf g}(i) ∑ i = 1 n g ( i ) 也类似，因为要计算的
n n n 都是某个
⌊ N x ⌋ \lfloor\frac Nx\rfloor ⌊ x N ⌋ ，所以这个
g \bf g g 的前缀和也可以再套一层杜教筛qaq。
2.例题 Description 给定
n ≤ 2 31 − 1 n\leq 2^{31}-1 n ≤ 2 31 − 1 ，求：
S φ ( n ) = ∑ i = 1 n φ ( n ) {\bf S}_{\varphi}(n)=\sum_{i=1}^n\varphi(n) S φ ( n ) = ∑ i = 1 n φ ( n ) ，以及
S μ ( n ) = ∑ i = 1 n μ ( n ) {\bf S}_{\mu}(n)=\sum_{i=1}^n\mu(n) S μ ( n ) = ∑ i = 1 n μ ( n ) 。
Solution 首先两个答案一定在
long long 和
int 范围内，因为
0 ≤ φ ( n ) ≤ n , − 1 ≤ μ ( n ) ≤ 1 0\leq\varphi(n)\leq n,-1\leq\mu(n)\leq1 0 ≤ φ ( n ) ≤ n , − 1 ≤ μ ( n ) ≤ 1 。
杜教筛的难点在于，给定一个
f ( n ) {\bf f}(n) f ( n ) ，要找一个合适的函数
g ( n ) {\bf g}(n) g ( n ) 使
g , f ∗ g {\bf g},{\bf f*g} g , f ∗ g 的前缀和都可以快速计算。
对于
φ ( n ) \varphi(n) φ ( n ) ，我们知道
φ = μ ∗ i d , φ ∗ 1 = i d \varphi=\mu*{\bf id},\varphi*{\bf 1}={\bf id} φ = μ ∗ id , φ ∗ 1 = id 。所以选取
g ( n ) = 1 {\bf g}(n)=1 g ( n ) = 1 即可，此时
( f ∗ g ) ( n ) = n ({\bf f*g})(n)=n ( f ∗ g ) ( n ) = n ，很容易求和。
对于
μ ( n ) \mu(n) μ ( n ) ，选取
g ( n ) = 1 {\bf g}(n)=1 g ( n ) = 1 也可，此时
( f ∗ g ) = ϵ ( n ) = [ n = 1 ] ({\bf f*g})=\epsilon(n)=[n=1] ( f ∗ g ) = ϵ ( n ) = [ n = 1 ] ，也很容易求和。
Code 下面给出求
S φ {\bf S}_\varphi S φ 的代码：
CPP typedef long long LL;
const int maxn = 2147483647 ;
const int maxm = 2000000 ;
LL S1[maxm], S2[1300 ];
bool vis[1300 ];
int N;
LL S (int n) {
if (n < maxm) return S1[n];
int x = N / n;
if (vis[x]) return S2[x];
vis[x] = true ;
LL &ans = S2[x];
ans = (LL)n * (n + 1 ) / 2 ;
for (int i = 2 , j; i <= n; i = j + 1 ) {
j = n / (n / i);
ans -= (j - i + 1 ) * S (n / i);
}
return ans;
}
代码中
maxn, maxm, 1300 分别是
N , N 2 3 , N 1 3 N,N^{\frac23},N^{\frac13} N , N 3 2 , N 3 1 的最大值，
S1[i] 在执行之前应预处理，是当
n ≤ N 2 3 n\leq N^{\frac23} n ≤ N 3 2 时的
S φ ( n ) {\bf S}_\varphi(n) S φ ( n ) 。
S2[x],vis[x] 用来记忆化
S φ ( ⌊ N x ⌋ ) {\bf S}_\varphi(\lfloor\frac Nx\rfloor) S φ (⌊ x N ⌋) 。
至于代码中的第一句注释，则是因为
⌊ N n ⌋ \lfloor\frac Nn\rfloor ⌊ n N ⌋ 是使得
x n ≤ N ⟺ ⌊ N x ⌋ ≥ n xn\leq N\iff\lfloor\frac Nx\rfloor\geq n x n ≤ N ⟺ ⌊ x N ⌋ ≥ n 的最大正整数
x x x 。如果这个
x x x 还不满足
⌊ N x ⌋ = n \lfloor\frac Nx\rfloor=n ⌊ x N ⌋ = n 的话，就不可能存在其他
x x x 了。
Description 给定
n n n ，求
∑ i = 1 n ∑ j = 1 n ( i j gcd ( i , j ) ) \sum_{i=1}^n\sum_{j=1}^n(ij\gcd(i,j)) ∑ i = 1 n ∑ j = 1 n ( ij g cd( i , j ))
对
p p p 取模。
n , m ≤ 10 10 , 5 × 10 8 ≤ p ≤ 1.1 × 10 9 n,m\leq10^{10},5\times10^8\leq p\leq1.1\times10^9 n , m ≤ 1 0 10 , 5 × 1 0 8 ≤ p ≤ 1.1 × 1 0 9 且
p p p 是质数。时限 6s。
Solution 首先有
∑ i = 1 n ∑ j = 1 n ( i j gcd ( i , j ) ) = ∑ i = 1 n ∑ j = 1 n ( i j ∑ d ∣ i , d ∣ j φ ( d ) ) = ∑ d = 1 n φ ( d ) ( ∑ 1 ≤ i ≤ n , d ∣ i i ) ( ∑ 1 ≤ j ≤ n , d ∣ j j ) = ∑ d = 1 n d 2 φ ( d ) S ( ⌊ n d ⌋ ) 2 \begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n(ij\gcd(i,j))\\=&\sum_{i=1}^n\sum_{j=1}^n\left(ij\sum_{d\mid i,d\mid j}\varphi(d)\right)\\=&\sum_{d=1}^{n}\varphi(d)\left(\sum_{1\leq i\leq n,d\mid i}i\right)\left(\sum_{1\leq j\leq n,d\mid j}j\right)\\=&\sum_{d=1}^{n}d^2\varphi(d)S\left(\left\lfloor\frac nd\right\rfloor\right)^2\end{aligned} = = = i = 1 ∑ n j = 1 ∑ n ( ij g cd( i , j )) i = 1 ∑ n j = 1 ∑ n ij d ∣ i , d ∣ j ∑ φ ( d ) d = 1 ∑ n φ ( d ) 1 ≤ i ≤ n , d ∣ i ∑ i 1 ≤ j ≤ n , d ∣ j ∑ j d = 1 ∑ n d 2 φ ( d ) S ( ⌊ d n ⌋ ) 2
式中
S ( k ) = ∑ i = 1 k i = k ( k + 1 ) 2 S(k)=\sum_{i=1}^k i=\frac{k(k+1)}2 S ( k ) = ∑ i = 1 k i = 2 k ( k + 1 ) 。第一步等式是因为
∑ d ∣ k φ ( d ) = k \sum_{d\mid k}\varphi(d)=k ∑ d ∣ k φ ( d ) = k 。第二步等式是交换了求和顺序，把对
d d d 的求和放到最外层。第三步等式是把两个括号里的公因数
d d d 提出来。
根据老套路，我们数论分块，并对每一块的
d 2 φ ( d ) d^2\varphi(d) d 2 φ ( d ) 求区间和。
考虑使用杜教筛计算两个区间和相减。但是一个问题是时间复杂度。
假设我们已经有了函数
LL S(LL n) 用来求
d 2 φ ( d ) d^2\varphi(d) d 2 φ ( d ) 的前缀和，那么接下来应该这样：
CPP for (int i = 1 , j; i <= n && i <= m; i = j + 1 ) {
j = n / (n / i);
LL t = Sum (n / i);
ans = (ans + (S (j) - S (i - 1 )) * t % p * t % p) % p;
}
可以发现
j 始终是某个
⌊ n x ⌋ \lfloor\frac nx\rfloor ⌊ x n ⌋ ，而
i-1 就是上一次的
j ，自然也是某个
⌊ n x ⌋ \lfloor\frac nx\rfloor ⌊ x n ⌋ 。从而恰好用到了杜教筛所有的递归计算，仍然只有
O ( n 2 3 ) O(n^{\frac23}) O ( n 3 2 ) 的复杂度。
第二个问题是对于
f ( n ) = n 2 φ ( n ) {\bf f}(n)=n^2\varphi(n) f ( n ) = n 2 φ ( n ) ，如何找到合适的
g {\bf g} g 。
考虑在数论函数的狄利克雷卷积之外定义点乘
f ⋅ g {\bf f\cdot g} f ⋅ g ，指逐项相乘，即
( f ⋅ g ) ( n ) = f ( n ) g ( n ) ({\bf f\cdot g})(n)={\bf f}(n){\bf g}(n) ( f ⋅ g ) ( n ) = f ( n ) g ( n ) ；定义函数
f ( n ) {\bf f}(n) f ( n ) 是完全积性函数，当且仅当对于所有的
n , m n,m n , m 都有
f ( n m ) = f ( n ) f ( m ) {\bf f}(nm)={\bf f}(n){\bf f}(m) f ( nm ) = f ( n ) f ( m ) 。像
ϵ ( n ) = [ n = 1 ] , i d k ( n ) = n k \epsilon(n)=[n=1],{\bf id}^k(n)=n^k ϵ ( n ) = [ n = 1 ] , id k ( n ) = n k 都在此列。
引理 2.1
若
f {\bf f} f 是完全积性函数，
g , h {\bf g, h} g , h 是数论函数，则
( f ⋅ g ) ∗ ( f ⋅ h ) = f ⋅ ( g ∗ h ) ({\bf f\cdot g})*({\bf f\cdot h})={\bf f}\cdot({\bf g*h}) ( f ⋅ g ) ∗ ( f ⋅ h ) = f ⋅ ( g ∗ h ) 。
证明是很显然的：
( ( f ⋅ g ) ∗ ( f ⋅ h ) ) ( n ) = ∑ d ∣ n f ( d ) g ( d ) f ( n d ) h ( n d ) = f ( n ) ∑ d ∣ n g ( d ) h ( n d ) = ( f ⋅ ( g ∗ h ) ) ( n ) \begin{aligned}&\left(({\bf f\cdot g})*({\bf f\cdot h})\right)(n)\\=&\sum_{d\mid n}{\bf f}(d){\bf g}(d){\bf f}\left(\frac nd\right){\bf h}\left(\frac nd\right)\\=&{\bf f}(n)\sum_{d\mid n}{\bf g}(d){\bf h}\left(\frac nd\right)\\=&\left({\bf f}\cdot({\bf g*h})\right)(n)\end{aligned} = = = ( ( f ⋅ g ) ∗ ( f ⋅ h ) ) ( n ) d ∣ n ∑ f ( d ) g ( d ) f ( d n ) h ( d n ) f ( n ) d ∣ n ∑ g ( d ) h ( d n ) ( f ⋅ ( g ∗ h ) ) ( n ) 由此，对于
f ( n ) = n 2 φ ( n ) {\bf f}(n)=n^2\varphi(n) f ( n ) = n 2 φ ( n ) ，即
f = i d 2 ⋅ φ {\bf f}={\bf id}^2\cdot\varphi f = id 2 ⋅ φ ，可取
g = i d 2 ⋅ 1 {\bf g}={\bf id}^2\cdot{\bf 1} g = id 2 ⋅ 1 ，则根据上述引理有
f ∗ g = i d 2 ⋅ ( φ ∗ 1 ) {\bf f*g}={\bf id}^2\cdot(\varphi*{\bf 1}) f ∗ g = id 2 ⋅ ( φ ∗ 1 ) ，即
f ∗ g = i d 3 {\bf f*g}={\bf id}^3 f ∗ g = id 3 。
所以令
g ( n ) = n 2 ⋅ 1 = n 2 {\bf g}(n)=n^2\cdot1=n^2 g ( n ) = n 2 ⋅ 1 = n 2 ，则立得
S ( n ) = ∑ i = 1 n i 3 − ∑ i = 2 n i 2 S ( ⌊ n i ⌋ ) {\bf S}(n)=\sum_{i=1}^ni^3-\sum_{i=2}^ni^2{\bf S}\left(\left\lfloor\frac ni\right\rfloor\right) S ( n ) = ∑ i = 1 n i 3 − ∑ i = 2 n i 2 S ( ⌊ i n ⌋ )
至于如何对
i 2 , i 3 i^2,i^3 i 2 , i 3 求和，我们有
∑ i = 1 n i 3 = n 2 ( n + 1 ) 2 4 \sum_{i=1}^ni^3=\frac{n^2(n+1)^2}4 ∑ i = 1 n i 3 = 4 n 2 ( n + 1 ) 2 ，
∑ i = 1 n i 2 = n ( n + 1 ) ( 2 n + 1 ) 6 \sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}6 ∑ i = 1 n i 2 = 6 n ( n + 1 ) ( 2 n + 1 ) 。
具体代码作为练习（雾），其实和上面的
φ ( n ) \varphi(n) φ ( n ) 的杜教筛是类似的。
3. BZOJ4176 Lucas的数论 这是权限题。
Description 给定
n n n ，求
∑ i = 1 n ∑ j = 1 n d ( i j ) \sum_{i=1}^n\sum_{j=1}^n{\bf d}(ij) ∑ i = 1 n ∑ j = 1 n d ( ij ) 。
d ( k ) {\bf d}(k) d ( k ) 是
k k k 的约数个数。
Solution 对于
d ( i j ) {\bf d}(ij) d ( ij ) ，考虑某个
d ∣ i j d\mid ij d ∣ ij 来说，令
a = i gcd ( i , d ) , b = d gcd ( i , d ) a=\frac i{\gcd(i,d)},b=\frac d{\gcd(i,d)} a = g c d ( i , d ) i , b = g c d ( i , d ) d ，显然
a ⊥ b , a ∣ i , b ∣ j a\perp b,a\mid i,b\mid j a ⊥ b , a ∣ i , b ∣ j （前两个显然，最后一个是因为
b gcd ( i , d ) ∣ i j ⇒ b ∣ a j ⇒ b ∣ j b\gcd(i,d)\mid ij\Rightarrow b\mid aj\Rightarrow b\mid j b g cd( i , d ) ∣ ij ⇒ b ∣ aj ⇒ b ∣ j 。最后一步是因为
a ⊥ b a\perp b a ⊥ b ）。另外，任意给定两个数
a , b a,b a , b 使得
a ⊥ b , a ∣ i , b ∣ j a\perp b,a\mid i,b\mid j a ⊥ b , a ∣ i , b ∣ j 都有
d = i a b ∣ i j d=\frac iab\mid ij d = a i b ∣ ij ，且
i gcd ( i , d ) = a , d gcd ( i , d ) = b \frac i{\gcd(i,d)}=a,\frac d{\gcd(i,d)}=b g c d ( i , d ) i = a , g c d ( i , d ) d = b 。 由此可知
∑ d ∣ i j 1 = ∑ a ∣ i , b ∣ j , a ⊥ b 1 = ∑ a ∣ i , b ∣ j [ a ⊥ b ] \sum_{d\mid ij}1=\sum_{a\mid i,b\mid j,a\perp b}1=\sum_{a\mid i,b\mid j}[a\perp b] ∑ d ∣ ij 1 = ∑ a ∣ i , b ∣ j , a ⊥ b 1 = ∑ a ∣ i , b ∣ j [ a ⊥ b ] 所以
a n s = ∑ i = 1 n ∑ j = 1 n d ( i j ) = ∑ i = 1 n ∑ j = 1 n ∑ a ∣ i ∑ b ∣ j [ a ⊥ b ] = ∑ i = 1 n ∑ j = 1 n ∑ a ∣ i ∑ b ∣ j ∑ d ∣ a , d ∣ b μ ( d ) = ∑ d = 1 n μ ( d ) ( ∑ d ∣ a ∑ a ∣ i ≤ n 1 ) ( ∑ d ∣ b ∑ b ∣ j ≤ n 1 ) = ∑ d = 1 n μ ( d ) ( ∑ a = 1 ⌊ n d ⌋ ⌊ ⌊ n d ⌋ a ⌋ ) 2 \begin{aligned}ans=&\sum_{i=1}^n\sum_{j=1}^n{\bf d}(ij)\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{a\mid i}\sum_{b\mid j}[a\perp b]\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{a\mid i}\sum_{b\mid j}\sum_{d\mid a,d\mid b}\mu(d)\\=&\sum_{d=1}^n\mu(d)\left(\sum_{d\mid a}\sum_{a\mid i\leq n}1\right)\left(\sum_{d\mid b}\sum_{b\mid j\leq n}1\right)\\=&\sum_{d=1}^n\mu(d)\left(\sum_{a=1}^{\lfloor\frac nd\rfloor}\left\lfloor\frac {\lfloor\frac nd\rfloor}a\right\rfloor\right)^2\end{aligned} an s = = = = = i = 1 ∑ n j = 1 ∑ n d ( ij ) i = 1 ∑ n j = 1 ∑ n a ∣ i ∑ b ∣ j ∑ [ a ⊥ b ] i = 1 ∑ n j = 1 ∑ n a ∣ i ∑ b ∣ j ∑ d ∣ a , d ∣ b ∑ μ ( d ) d = 1 ∑ n μ ( d ) d ∣ a ∑ a ∣ i ≤ n ∑ 1 d ∣ b ∑ b ∣ j ≤ n ∑ 1 d = 1 ∑ n μ ( d ) a = 1 ∑ ⌊ d n ⌋ ⌊ a ⌊ d n ⌋ ⌋ 2
令
F ( n ) = ∑ i = 1 n ⌊ n i ⌋ = ∑ i = 1 n ∑ i j ≤ n 1 = ∑ t = 1 n d ( t ) F(n)=\sum_{i=1}^n\left\lfloor\frac ni\right\rfloor=\sum_{i=1}^n\sum_{ij\leq n}1=\sum_{t=1}^n{\bf d}(t) F ( n ) = ∑ i = 1 n ⌊ i n ⌋ = ∑ i = 1 n ∑ ij ≤ n 1 = ∑ t = 1 n d ( t ) ，
a n s = ∑ d = 1 n μ ( d ) F ( ⌊ n d ⌋ ) 2 ans=\sum_{d=1}^n\mu(d)F\left(\left\lfloor\frac nd\right\rfloor\right)^2 an s = ∑ d = 1 n μ ( d ) F ( ⌊ d n ⌋ ) 2
对
d d d 数论分块，则需要快速求出
μ ( d ) \mu(d) μ ( d ) 的前缀和与
F ( ⌊ n d ⌋ ) F\left(\left\lfloor\frac nd\right\rfloor\right) F ( ⌊ d n ⌋ ) 。前者可以直接杜教筛；后者可以借鉴杜教筛的思想。
考虑到单次计算
F ( n ) F(n) F ( n ) 复杂度为
O ( n ) O(\sqrt n) O ( n ) （数论分块），而预处理
F ( 1 ) … F ( n ) F(1)\dots F(n) F ( 1 ) … F ( n ) 复杂度是
O ( n ) O(n) O ( n ) （因为可以线性筛出
d {\bf d} d ，则可以预处理出
F ( 1 ) … F ( n 2 3 ) F(1)\dots F(n^{\frac23}) F ( 1 ) … F ( n 3 2 ) ，后面的
F F F 依次
O ( n ) O(\sqrt n) O ( n ) 算，复杂度仍然是
O ( n 2 3 ) O(n^{\frac23}) O ( n 3 2 ) 。
虽然实际上这道题不预处理的话
O ( n 3 4 ) O(n^{\frac34}) O ( n 4 3 ) 也能过，但是无所谓了qaq。
4. 奇怪的题目 Description 给定
n n n ，求
∑ i = 1 n ( μ 2 ∗ ( i d ⋅ μ ) ) ( i ) \sum_{i=1}^n(\mu^2*({\bf id}\cdot\mu))(i) ∑ i = 1 n ( μ 2 ∗ ( id ⋅ μ )) ( i ) 。
其中
n ≤ 10 9 n\leq10^9 n ≤ 1 0 9 ，
μ 2 ( n ) = ( μ ( n ) ) 2 \mu^2(n)=(\mu(n))^2 μ 2 ( n ) = ( μ ( n ) ) 2 。
Solution 令
f = μ 2 ∗ ( i d ⋅ μ ) {\bf f}=\mu^2*({\bf id}\cdot\mu) f = μ 2 ∗ ( id ⋅ μ ) ，则
i d ∗ f = ( i d ∗ ( i d ⋅ μ ) ) ∗ μ 2 = μ 2 {\bf id}*f=({\bf id}*({\bf id}\cdot\mu))*\mu^2=\mu^2 id ∗ f = ( id ∗ ( id ⋅ μ )) ∗ μ 2 = μ 2 。所以取
g ( n ) = n {\bf g}(n)=n g ( n ) = n ，因此
S ( n ) = ∑ i = 1 n μ 2 ( i ) − ∑ i = 2 n i S ( ⌊ n i ⌋ ) {\bf S}(n)=\sum_{i=1}^n\mu^2(i)-\sum_{i=2}^ni{\bf S}\left(\left\lfloor\frac ni\right\rfloor\right) S ( n ) = ∑ i = 1 n μ 2 ( i ) − ∑ i = 2 n i S ( ⌊ i n ⌋ )
剩下的就是如何计算
∑ i = 1 n μ 2 ( i ) \sum_{i=1}^n\mu^2(i) ∑ i = 1 n μ 2 ( i ) 。
可以发现
μ 2 ( i ) = [ i 不含平方因子 ] \mu^2(i)=[i\text{不含平方因子}] μ 2 ( i ) = [ i 不含平方因子 ] 。所以定义
s ( i ) = max d 2 ∣ i d {\bf s}(i)=\max_{d^2\mid i}d s ( i ) = max d 2 ∣ i d ，则
μ 2 ( i ) = [ s ( i ) = 1 ] \mu^2(i)=[{\bf s}(i)=1] μ 2 ( i ) = [ s ( i ) = 1 ] 。
容易发现
d 2 ∣ i ⟺ d ∣ s ( i ) d^2\mid i\iff d\mid{\bf s}(i) d 2 ∣ i ⟺ d ∣ s ( i ) ， 所以
∑ i = 1 n μ 2 ( i ) = ∑ i = 1 n [ s ( i ) = 1 ] = ∑ i = 1 n ∑ d 2 ∣ i μ ( d ) = ∑ d = 1 ⌊ n ⌋ μ ( d ) ⌊ n d 2 ⌋ \sum_{i=1}^n\mu^2(i)=\sum_{i=1}^n[{\bf s}(i)=1]=\sum_{i=1}^n\sum_{d^2\mid i}\mu(d)=\sum_{d=1}^{\lfloor\sqrt n\rfloor}\mu(d)\left\lfloor\frac n{d^2}\right\rfloor ∑ i = 1 n μ 2 ( i ) = ∑ i = 1 n [ s ( i ) = 1 ] = ∑ i = 1 n ∑ d 2 ∣ i μ ( d ) = ∑ d = 1 ⌊ n ⌋ μ ( d ) ⌊ d 2 n ⌋
可以暴力枚举
d d d ，在
O ( n ) O(\sqrt n) O ( n ) 时间内求出。由于杜教筛本来就有
O ( n ) O(\sqrt n) O ( n ) 的计算，这并不会增加复杂度。
3.贝尔级数 有的时候我们不太容易找到杜教筛的合适的
g {\bf g} g ，这时候有一个很厉害的东西：贝尔级数。
（Warning: 以下要求大致了解生成函数相关）
3.1 定义 对于积性函数
f ( n ) {\bf f}(n) f ( n ) ，定义
f {\bf f} f 模
p p p 的贝尔级数为
f p ( x ) = ∑ i = 0 ∞ f ( p i ) x i {\bf f}_p(x)=\sum_{i=0}^{\infty}{\bf f}(p^i)x^i f p ( x ) = ∑ i = 0 ∞ f ( p i ) x i
例如
ϵ p ( x ) = 1 , 1 p ( x ) = 1 1 − x , i d p k ( x ) = 1 1 − p k x , μ p ( x ) = 1 − x , d p ( x ) = 1 ( 1 − x ) 2 , φ p ( x ) = 1 − x 1 − p x \epsilon_p(x)=1,{\bf 1}_p(x)=\frac1{1-x},{\bf id}^k_p(x)=\frac1{1-p^kx},\mu_p(x)=1-x,{\bf d}_p(x)=\frac1{(1-x)^2},\varphi_p(x)=\frac{1-x}{1-px} ϵ p ( x ) = 1 , 1 p ( x ) = 1 − x 1 , id p k ( x ) = 1 − p k x 1 , μ p ( x ) = 1 − x , d p ( x ) = ( 1 − x ) 2 1 , φ p ( x ) = 1 − p x 1 − x 。
一个很好的性质是（实际上就是把狄利克雷卷积变成了一般卷积）
( f ∗ g ) p ( x ) = f p ( x ) g p ( x ) ({\bf f*g})_p(x)={\bf f}_p(x){\bf g}_p(x) ( f ∗ g ) p ( x ) = f p ( x ) g p ( x ) 接下来我们就要生拼硬凑出一些奇怪的例题了：
3.2 例题 令积性函数
f {\bf f} f 满足
f ( p c ) = p c + [ c > 0 ] ( − 1 ) c {\bf f}(p^c)=p^c+[c>0](-1)^c f ( p c ) = p c + [ c > 0 ] ( − 1 ) c ，求
f {\bf f} f 的前缀和。
可以发现
f p ( x ) = − 1 + ∑ i = 0 ∞ ( p i x i + ( − 1 ) i x i ) = 1 1 − p x + 1 1 + x − 1 {\bf f}_p(x)=-1+\sum_{i=0}^{\infty}\left(p^ix^i+(-1)^ix^i\right)=\frac1{1-px}+\frac1{1+x}-1 f p ( x ) = − 1 + ∑ i = 0 ∞ ( p i x i + ( − 1 ) i x i ) = 1 − p x 1 + 1 + x 1 − 1 ， 所以取
g p ( x ) = ( 1 − p x ) ( 1 + x ) {\bf g}_p(x)=(1-px)(1+x) g p ( x ) = ( 1 − p x ) ( 1 + x ) ，即得
( f ∗ g ) p ( x ) = 1 + x + 1 − p x − ( 1 − p x ) ( 1 + x ) = 1 + p x 2 ({\bf f*g})_p(x)=1+x+1-px-(1-px)(1+x)=1+px^2 ( f ∗ g ) p ( x ) = 1 + x + 1 − p x − ( 1 − p x ) ( 1 + x ) = 1 + p x 2
所以问题转化成了如何求
g {\bf g} g 的前缀和，以及如何求
h p ( x ) = 1 + p x 2 {\bf h}_p(x)=1+px^2 h p ( x ) = 1 + p x 2 的前缀和。
显然可知
( 1 − p x ) (1-px) ( 1 − p x ) 对应
i d ⋅ μ {\bf id}\cdot\mu id ⋅ μ ，而
( 1 + x ) (1+x) ( 1 + x ) 对应
μ 2 \mu^2 μ 2 。（指
μ 2 ( n ) = ( μ ( n ) ) 2 = ∣ μ ( n ) ∣ \mu^2(n)=(\mu(n))^2=|\mu(n)| μ 2 ( n ) = ( μ ( n ) ) 2 = ∣ μ ( n ) ∣ ）。
所以
g = ( i d ⋅ μ ) ∗ μ 2 {\bf g}=({\bf id}\cdot\mu)*\mu^2 g = ( id ⋅ μ ) ∗ μ 2 ，其前缀和可以通过之前的那道“奇怪的题目”的做法求出。
而对于
h ( n ) {\bf h}(n) h ( n ) 的前缀和，可以发现只有
n n n 是完全平方数，且每个质因数的指数都是 2 （等价于
μ ( n ) ≠ 0 \mu(\sqrt n)\neq0 μ ( n ) = 0 ）时
h ( n ) = n {\bf h}(n)=\sqrt n h ( n ) = n ，其他时候
h ( n ) = 0 {\bf h}(n)=0 h ( n ) = 0 。所以很显然的，
∑ i = 1 n h ( i ) = ∑ i = 1 ⌊ n ⌋ i μ 2 ( i ) \sum_{i=1}^n{\bf h}(i)=\sum_{i=1}^{\lfloor\sqrt n\rfloor}i\mu^2(i) ∑ i = 1 n h ( i ) = ∑ i = 1 ⌊ n ⌋ i μ 2 ( i )
枚举
i i i 即可在
O ( n ) O(\sqrt n) O ( n ) 时间内算出。所以本题解决了，复杂度是
O ( n 2 3 ) O(n^{\frac23}) O ( n 3 2 ) 。
4.总结 本篇文章，是一位在 OI 中数学方面小有名气的选手无私的馈赠。五道杜教筛例题，涵盖了杜教筛从入门到进阶的大部分套路。你可以通过这篇文章，对杜教筛进行较为深入的了解。详细的复杂度证明、精心挑选的例题和各种不同的套路与 trick，能让你对杜教筛有一个较为全面的掌握。作者相信，这篇漂亮的博客，可以给拼搏于 OI 的逐梦之路上的你，提供一个有力的援助。
本文在读者已经掌握莫比乌斯反演的基础上讲述了杜教筛，并提出了若干例题，涵盖了部分杜教筛题目的套路；既可以作为杜教筛的入门文章，又可以让部分选手更进一步地了解杜教筛，更是一篇不错的杜教筛复习博客。
【狄利克雷卷积及莫比乌斯反演】