杜教筛是要记忆化的。但是$map$的常数非常大，亲测$Hash Table$也很难跑过现在luogu上的杜教筛模板。怎么办呢？如果我们能够预处理出所有会被用到的数，给他们分配好空间，那么不仅可以避开$map$的常数，还可以从小到大依次枚举这些数进行处理，从而避免递归。
观察$S(n)=h(n)-\sum_{i=2}^n S(\lfloor{n\over i}\rfloor)$，可知会被取到的数可以分为两类：
1.小于$\sqrt n$的所有自然数
2.一个大于$\sqrt n$的数$x$，并且存在一个小于$\sqrt n$的数，使$\lfloor {n\over i}\rfloor = x$成立。
由此也可以看出来，可能被取的数只有$2\cdot \sqrt n$个。
那么可以一次性处理出来所有要计算的$n$。从小到大枚举$i$，当$\lfloor {n\over i}\rfloor$大于$2e6$（就是最初线筛出来的一部分前缀和，取$n^{2\over 3}$时最优秀）退出。
还有一个问题，我们在进行杜教筛的时候，怎么知道$n$在数组中对应的位置呢？
有一个结论，是$[1,\sqrt n]$中的每一个数$i$，$\lfloor{n\over i}\rfloor$唯一地映射到了一个大于$\sqrt n$的数；每一个大于$\sqrt n$、并且可以被$\lfloor{n\over i}\rfloor$映射到的数$x$，$\lfloor {n\over x} \rfloor $会映射到$i$，并且对于所有的会被映射到的数$x$，只有一个数的$\lfloor {n\over x}\rfloor$会等于$i$。
因此，从小到大枚举$i$，并且按照$i$的大小顺序将$\lfloor {n\over i}\rfloor$存入数组，那么对于大于$\sqrt n$的$x$数组中的第$n\over x$个位置就是这个数所在的位置。
然后就可以愉快地杜教筛啦~~
下面是luogu杜教筛模板：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void read(T &x)
{
x=0; char c=getchar(); int f=1;
while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=2e6+10;
int flg[N],pri[N],num,m;
ll mu[N],phi[N];
void predo()
{
m=2e6;
phi[1]=1,mu[1]=1;
for(int i=2;i<=m;++i)
{
if(!flg[i]) pri[num++]=i,phi[i]=i-1,mu[i]=-1;
for(int j=0;j<num&&pri[j]*i<=m;++j)
{
flg[i*pri[j]]=1;
if(i%pri[j]) mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*(pri[j]-1);
else{ phi[i*pri[j]]=phi[i]*pri[j]; break;}
}
}
for(int i=1;i<=m;++i) phi[i]+=phi[i-1],mu[i]+=mu[i-1];
}
ll Mu[N],Phi[N];
int v[N],top,n;
inline ll qphi(int x){return x<=m?phi[x]:Phi[n/x];}
inline ll qmu(int x){return x<=m?mu[x]:Mu[n/x];}
int main()
{
int T; read(T); predo();
while(T--)
{
read(n); top=0;
for(int i=1;i<=n;++i)
{
if((n/i)<=m) break;
v[++top]=n/i;
}
for(int i=top;i;--i)
{
int t=v[i];
ll ap=t*(ll)(t+1)/2,am=1;
for(int l=2,r=1;r<t;l=r+1) r=t/(t/l),ap-=qphi(t/l)*(r-l+1),am-=qmu(t/l)*(r-l+1);
Phi[i]=ap,Mu[i]=am;
}
printf("%lld %lld\n",qphi(n),qmu(n));
}
return 0;
}
|