先不讲什么是杜教筛,先讲什么是迪利克雷卷积。
迪利克雷卷积
定义两个函数的迪利克雷卷积:$(f \ast g)(n) = \sum_{d|n}f(d) \times g(n/d)$
$(f \ast g)(n)$表示有一个函数$h=f*g$,$(f \ast g)(n)$就是$h(n)$,说白了就是先把$(f \ast g)$看成一个函数$h$,再看后面的$(n)$
我们来看一下迪利克雷卷积中的常见函数:
$$
1.\varphi(n) \\\
2.\mu(n) \\\
3.id(n) \\\
4.I(n) \\\
5.\varepsilon(n) \\\
$$
简单介绍一下:
$\varphi(n)$就是欧拉函数,这个可以去看算法基础课。
$\mu(n)$是莫比乌斯函数,可以去看算法提高课或者看莫比乌斯反演(基础)的前面一部分。
$id(n)$这个就简单很多了,$id(n)=n$
$I(n)$更简单,$I(n)=1$
$\varepsilon(n)$几乎弱智,$n$如果是$1$,$\varepsilon(n)$就是1,否则为0
那这些函数有什么关系或者性质吗?有,而且很重要,来列举几个:
$1.f \ast \varepsilon=f$,这个显然
$2.id \ast \mu=\varphi,\varphi \ast I=id$,这个在莫比乌斯反演(基础)里面证过
$3.\mu \ast I=\varepsilon$,这个用容斥即可
现在,让我们试着证明莫比乌斯反演。
$$
f \ast I=g \\\
\Leftrightarrow f \ast I \ast \mu=g \ast \mu \\\
\Leftrightarrow f \ast \varepsilon=g \ast \mu \\\
\Leftrightarrow f=g \ast \mu \\\
$$
就这样证完了?这个十分神奇的莫比乌斯反演用迪利克雷卷积竟然证明的如此简单。
杜教筛
杜教筛是用来快速求一个积性函数的前缀和的方法。
有一个积性函数$f$,现在我们要求$\sum_{i=1}^n f(i)$,设其为$S(n)$。
马上,整个杜教筛最关键的一步就要来了。
我们先再找一个积性函数$g$,求$\sum_{i=1}^n (f \ast g)(i)$。
$$
\sum_{i=1}^n (f \ast g)(i) \\\
=\sum_{i=1}^n \sum_{d|i} f(d) \times g(\frac{i}{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)$
$$
g(1)S(n) \\\
=\sum_{i=1}^n g(i)S([\frac{n}{i}])-\sum_{i=2}^n g(i)S([\frac{n}{i}]) \\\
=\sum_{i=1}^n (f \ast g)(i)-\sum_{i=2}^n g(i)S([\frac{n}{i}]) \\\
$$
所以,杜教筛的结论出来了:
$$
g(1)S(n)=\sum_{i=1}^n (f \ast g)(i)-\sum_{i=2}^n g(i)S([\frac{n}{i}])
$$
那么,只要我们找到一个合适的$g$,就能求出$S(n)$。
$g$需要满足什么条件?只要$g(1)$容易求(这基本上所有积性函数都满足),且$f \ast g$和$g$的前缀和能很快算出来(这就看你的构造能力)即可。
那么现在,让我们做一道模板题试试手吧!
例题
例题1:杜教筛(Sum)
先看$\mu$的前缀和,因为$\mu \ast I=\varepsilon$所以我们的$g$显然应该选$I$。
那么可以把筛$\mu$的部分写出来:
LL S2(LL n)//S2是用来筛莫比乌斯函数的
{
if(n==1)return 1;
LL l=2,r;
LL s=1;
while(l<=n){
r=n/(n/l);
s-=(r-l+1)*S2(n/l);
l=r+1;
}
return s;
}
但是这样显然还过不了这道题。
我们可以加上一个哈希表,进行记忆化从而优化时间复杂度。
写出来是这样的
LL S2(LL n)//S2是用来筛莫比乌斯函数的
{
if(n==1)return 1;
if(mp2.count(n)>0)return mp2[n];//用来存莫比乌斯函数前缀和的mp2
LL l=2,r;
LL s=1;
while(l<=n){
r=n/(n/l);
s-=(r-l+1)*S2(n/l);
l=r+1;
}
mp2[n]=s;
return s;
}
还可以继续优化,用线性筛筛出前$n^{\frac{2}{3}}$个数的前缀和。
LL S2(LL n)//S2是用来筛莫比乌斯函数的
{
if(n<=X)return s2[n];//线性筛筛出的s2
if(mp2.count(n)>0)return mp2[n];//用来存莫比乌斯函数前缀和的mp2
LL l=2,r;
LL s=1;
while(l<=n){
r=n/(n/l);
s-=(r-l+1)*S2(n/l);
l=r+1;
}
mp2[n]=s;
return s;
}
筛欧拉函数的也差不多,直接看下面完整代码吧👇。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL X=2e6;
LL n;
LL p[X+10],t,mu[X+10],phi[X+10],s1[X+10],s2[X+10];
bool st[X+10];
unordered_map<LL,LL> mp1,mp2;
void get_prime()
{
mu[1]=phi[1]=1;
for(LL i=2;i<=X;i++){
if(!st[i])p[++t]=i,mu[i]=-1,phi[i]=i-1;
for(LL j=1;p[j]*i<=X;j++){
st[i*p[j]]=1;
if(i%p[j]==0){
mu[i*p[j]]=0;
phi[i*p[j]]=phi[i]*p[j];
break;
}
mu[i*p[j]]=-mu[i];
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
for(LL i=1;i<=X;i++)
s2[i]=s2[i-1]+mu[i],s1[i]=s1[i-1]+phi[i];
}
LL S1(LL n)
{
if(n<=X)return s1[n];
if(mp1.count(n)>0)return mp1[n];
LL l=2,r;
LL s=n*(n+1)/2;
while(l<=n){
r=n/(n/l);
s-=(r-l+1)*S1(n/l);
l=r+1;
}
mp1[n]=s;
return s;
}
LL S2(LL n)
{
if(n<=X)return s2[n];
if(mp2.count(n)>0)return mp2[n];
LL l=2,r;
LL s=1;
while(l<=n){
r=n/(n/l);
s-=(r-l+1)*S2(n/l);
l=r+1;
}
mp2[n]=s;
return s;
}
int main()
{
get_prime();
LL t;
cin>>t;
while(t--){
cin>>n;
cout<<S1(n)<<' '<<S2(n)<<endl;
}
}
致敬dls