杜教筛专题总结

莫名其妙地写完了杜教筛的几道题？

然而理解还是不怎么深刻啊

主要是经常忘记谁·谁=谁

1.常用卷积

[egin{aligned} mu * 1 &= epsilon \ mu * id &= varphi \ varphi * 1 &= id \ 1 * 1 &= d \ mu * d &= 1 \ id * 1 &= sigma \ end{aligned}]

2.常用公式

[egin{aligned} left [ n==1 ight ] &= sum limits_{d|n} mu(d) \ n &=sum limits_{d|n} varphi(d) \ varphi(ab) &= frac{varphi(a)varphi(b)gcd(a,b)}{varphi(gcd(a,b))} \ sumlimits_{i=1}^{n}d(i) &=sumlimits_{i=1}^{n} left lfloor frac{n}{i} ight floor \ d(ij)&=sum_{x|i}sum_{y|j}[gcd(x,y)==1]\ gcd(x^a-1,x^b-1)&=x^{gcd(a,b)}-1\ gcd(f[a],f[b])&=f[gcd(a,b)](f为菲波那契数列) end{aligned}]

3.杜教筛(进入正题)

我们需要解决的是快速求得 (S(n)=sumlimits_{i=1}^{n}f(i))
考虑构造一个函数 (h) 使得 (h=f*g) (什么你问为什么？我怎么知道~~背过不就好了~~)

[egin{aligned} h(n)&=sum limits_{d|n}f(d)g(n/d) \ sumlimits_{n=1}^N h(n) &=sum_{n=1}^Nsum limits_{d|n}f(d)g(n/d)\ &=sum_{d=1}^{N}g(d)sum_{i=1}^{ frac{N}{d} }f(i)\ &=sum_{d=1}^{N}g(d)S(frac{N}{d})\ &=g(1)S(n)+sum_{d=2}^{N}g(d)S(frac{N}{d})\ end{aligned}]

然后得到了

[egin{aligned} g(1)S(N)&=sum_{i=1}^{N}h(i)-sum_{i=2}^{N}g(i)S(frac{N}{i}) end{aligned}]

也就这个柿子了

4.例题

(sum)
题意描述：求(sumlimits_{i=1}^{n}varphi(i)) 和 (sumlimits_{i=1}^{n}mu(i))
我们知道 (mu*1=epsilon) 和 (varphi*1=id)
代入柿子就完了

神犇和蒟蒻
题意：求 (sumlimits_{i=1}^{n}varphi(i^2)) 和 (sumlimits_{i=1}^nmu(i^2))
很容易得知第二个柿子只有 (i==1) 时有值，所以答案衡为 (1)
考虑第二个柿子，根据 (varphi(x)=xprodlimits_{i=1}^{k}(1-frac{1}{p_i})) 得 (varphi(x^2)=xvarphi(x))
所以要求的是 (S(n)=sumlimits_{i=1}^{n}ivarphi(i))
推一下：

[egin{aligned} h(n)&=f*g=sum_{d|n}(dvarphi(d))g(frac{n}{d})\ end{aligned}]

考虑怎么消掉这个 (d) ,令 (g=id)

[egin{aligned} 则h(n)&=sum_{d|n}d*varphi(d)*frac{n}{d}\ &=nsum_{d|n}varphi(d)\ &=n^2 end{aligned}]

再代入柿子就好了

[egin{aligned} g(1)S(n)&=sum_{i=1}^nh(i)-sum_{i=2}^ng(i)S(frac{n}{i})\ S(n)&=frac{n(n+1)(2n+1)}{6}-sum_{i=2}^niS(frac{n}{i}) end{aligned}]

(Lucas)的数论
题意描述：求 (sumlimits_{i=1}^nsumlimits_{j=1}^nd(ij))
我们知道 (f(ij)=sumlimits_{x|i}sumlimits_{y|j}[gcd(x,y)==1])
反演一下：

[egin{aligned} &sum_{i=1}^nsum_{j=1}^nf(ij)\ &=sum_{i=1}^nsum_{j=1}^nsum_{x|i}sum_{y|j}[gcd(x,y)==1]\ &=sum_{i=1}^nsum_{j=1}^nsum_{x|i}sum_{y|j}sum_{d|gcd(x,y)}mu(d)\ &=sum_{x=1}^nsum_{y=1}^nleft lfloor frac{n}{i} ight floor left lfloor frac{n}{j} ight floorsum{d|gcd(i,j)}mu(d)\ &=sum_{d=1}^nmu(d)sum_{i=1}^{left lfloor frac{n}{d} ight floor}left lfloor frac{n}{id} ight floor sum_{j=1}^{left lfloor frac{n}{d} ight floor}left lfloor frac{n}{jd} ight floor\ &=sum_{d=1}^nmu(d)(sum_{i=1}^{left lfloor frac{n}{d} ight floor}left lfloor frac{n}{id} ight floor)^2\ end{aligned}]

发现 (sumlimits_{i=1}^{left lfloor frac{n}{d} ight floor}left lfloor frac{n}{id} ight floor)^2) 可以在 (O(sqrt{left lfloor frac{n}{d} ight floor})) 时间内得到

再把前面的 (mu) 杜教筛一下就没了

选数
题意描述：求 ([L,H]) 中选 (N) 个数最大公约数为 (K) 的方案数
这题俩做法啊

先说简单的，我们考虑将 (N) 个数都相等和不全相等分开考虑
然后把 (L) 变成 (left lceil frac{L}{K} ight ceil),(H) 变成 (left lfloor frac{H}{K} ight floor)
现在问题变成了从 ([L,H]) 中选 (N) 个不全相同的数使得他们 (gcd) 为 (1)
直接不好计算，考虑容斥
设 (f(x)) 表示 ([L,H]) 中最大公约数为 (x) 的方案数，(F(x)) 表示 ([L,H]) 中最大公约数为 (x) 的倍数的方案数
显然的，有 (f(x)=F(x)-sum_{x|d}f(d),F(x)=(left lfloor frac{H}{x} ight floor-left lfloorfrac{L-1}{x} ight floor)^N)
而如果 (x>H-L) 则 ([L,H]) 中至多有 (1) 种 (x) 的倍数，所以对答案没有贡献
所以从 (H-L) 枚举到 (1) 就行了
复杂度 (O((H-L)ln(H-L)))

然后是杜教筛做法
同样把 (L) 变成 (left lceil frac{L}{K} ight ceil),(H) 变成 (left lfloor frac{H}{K} ight floor)
反演一下$$egin{aligned}
&sum_{a=L}^Hsum_{b=L}^H...sum_{k=L}^H[gcd(a,b...k)==1]
&=sum_{a=L}^Hsum_{b=L}^H...sum_{k=L}^Hsum_{d|gcd(a,b...k)}mu(d)
&=sum_{d=1}^{H}mu(d)(left lfloor frac{H}{d} ight floor-left lfloor frac{L-1}{d} ight floor)^N
end{aligned}$$

快速幂+杜教筛就没了

(DZY Loves Math IV)
题意描述：求(sumlimits_{i=1}^nsumlimits_{j=1}^mvarphi(ij))
观察到 (n) 很小可以枚举,考虑对于每个 (i) 如何求(sumlimits_{j=1}^mvarphi(ij))
观察 (varphi(x)=xprodlimits_{i=1}^{k}(1-frac{1}{p_i}))
发现我们可以把 (i=prod_{i=1}^kp_i^{e_i}) 分成两部分 (a=prodlimits_{i=1}^kp_i,b=prodlimits_{i=1}^kp_i^{e_i-1})
则 (varphi(i)=bvarphi(a))
设 (f(i,m)=sumlimits_{j=1}^mvarphi(ij))
推一下$$egin{aligned}
f(i,m)&=sumlimits_{j=1}^mvarphi(ij)
&=bsum_{j=1}^mvarphi(aj)
&=bsum_{j=1}^mvarphi(frac{a}{gcd(a,j)})varphi(j)gcd(a,j)
&=bsum_{j=1}^mvarphi(frac{a}{gcd(a,j)})varphi(j)sum_{k|gcd(a,j)}varphi(k)
&=bsum_{j=1}^mvarphi(j)sum_{k|gcd(a,j)}varphi(k)varphi(frac{a}{gcd(a,j)})
&=bsum_{j=1}^mvarphi(j)sum_{k|gcd(a,j)}varphi(frac{a}{k})
&=bsum_{k|a}^mvarphi(frac{a}{k})sum_{j=1}^{m/k}varphi(kj)
&=bsum_{k|a}^mvarphi(frac{a}{k})f(k,frac{m}{k})
end{aligned}$$
边界(f(1,m)=sumlimits_{i=1}^mvarphi(i) , f(n,1)=varphi(n) , f(n,0)=0)
(f(1,m)=sumlimits_{i=1}^mvarphi(i))，可以用杜教筛的方法在一次 (O(m^{frac{2}{3}})) 的时间复杂度内求出，
同时，我们还记忆化了所有 (varphi(leftlfloor frac{m}{n} ight floor)) 的值，所以这个复杂度只需要计算一次。
所以复杂度大概 (O(nsqrt{m}+m^{frac{2}{3}})) 算起来不太对但是跑得还挺快？