筛法入门
神秘算法。
符号与约定
约定 \(p\) 表示素数，\(\prod_i p_i^{c_i}\) 表示某个数的质因数分解。
\(f\ast g\) 表示 \(f\) 与 \(g\) 的狄利克雷卷积。大写字母 \(F(i)\) 表示对应小写字母 \(f(i)\) 的前缀和，即 \(F(n)=\sum_{i=1}^nf(i)\)（同理，\(G(i),g(i)\) 等也有类似关系）。
\([]\) 为艾佛森括号，表示若内部表达式为真，则值为 \(1\)，否则为 \(0\)。
线性筛
大部分人最早接触的筛法，最初级的用法是用来筛质数。
事实上一般还是线性筛用的最多。
质数
考虑一个合数含有至少两个质因子，那么从小到大枚举质数，枚举它的所有倍数打一个合数标记。后面每次遇到没标记的就是质数进行，否则就是合数。这个是埃式筛，根据神秘证明复杂度是 \(O(n\log \log n)\)。
如果每个合数只被标记一次，复杂度就能缩到 \(O(n)\) 了。一个想法是让每个合数只被它的最小质因子标记一次。那么先枚举 \(i\)，再枚举之前找到的质数 \(p\)，给 \(ip\) 打标记。如果第一次遇到 \(i\bmod p=0\) 说明现在 \(p\) 就是 \(i\) 的最小质因子，如果再往后枚举 \(p\)，那么 \(ip\) 就不是被最小质因子（即 \(i\) 的最小质因子）标记的。所以遇到 \(i\bmod p=0\) 就退出循环即可。
求积性函数的值
这玩意只用来筛素数也太浪费了。容易发现每次 \(i,p\) 要么互质，要么 \(p\) 是 \(i\) 的最小质因子。那么对于一个积性函数 \(f(i)\)，前一种情况有 \(f(ip)=f(i)f(p)\)，后一种情况有 \(f(ip)=f(\frac{i}{p^c})f(p^{c+1})\)，其中 \(c\) 是 \(i\) 中 \(p\) 的指数。
多数情况下如果要计算积性函数一般 \(f(p^c)\) 是好求的。于是可以记录每个数最小质因子的指数以及最小质因子以外部分的 \(f\) 值，就能比较方便地求任意积性函数了。复杂度 \(O(n)\)，因为每次访问下一个数是 \(O(1)\) 的，每个数至多访问一遍。
求欧拉函数/莫比乌斯函数的值
这两个也是积性函数，但是拎出来单独说一下。
欧拉函数比较特殊，根据通项公式 \(\varphi(n)=\prod_{i}p_i^{c_i-1}(p_i-1)\) 有 \(\varphi(p^c)=p\cdot \varphi(p^{c-1})\)，于是在 \(i\bmod p=0\) 时可以直接计算。
莫比乌斯函数就更特殊了，因为在某质因子质数大于 \(1\) 时值取 \(0\)，所以遇到 \(i\bmod p=0\) 时 \(\mu(ip)=0\)。
杜教筛
难度陡然上升。
为什么杜教筛叫筛呢？（我个人理解）注意到线性筛是通过更小的多个 \(f(n)\) 用较小的复杂度计算出更大的单个 \(f(n)\)，虽然真正计算过的函数值变多了，但是你真正算出 \(f(n)\) 所用的时间变少了。杜教筛也是如此，通过多计算几个值的方式降低整体复杂度。
主要思路
考虑一对数论函数 \(f,g\)，有如下关系：
因为每一对 \(xy\le n\) 都会产生 \(g(x)f(y)\) 的贡献，假如把前缀和拆开就会发现上述式子成立。
于是有：
假如 \(f\ast g\) 和 \(g\) 的前缀和都好算（可以 \(O(1)\) 或者低复杂度算），那么对前面这一堆数论分块，就能转化成 \(O(\sqrt{n})\) 个子问题。
于是得到了杜教筛的基本思路。构造 \(g\) 使得 \(f\ast g\) 和 \(g\) 的前缀和都好求。
注意到 \(\left\lfloor\frac{\left\lfloor\frac{a}{n}\right\rfloor}{m}\right\rfloor=\left\lfloor\frac{a}{nm}\right\rfloor\)，所以需要计算的 \(F(n')\) 都是 \(\left\lfloor\frac{n}{i}\right\rfloor\) 中出现过的。那么全部取出来从小往大计算即可（或者记忆化）。
复杂度证不来，就是 \(\left\lfloor\frac{n}{i}\right\rfloor\) 的每个取值开根号加起来，可以证明是 \(O(n^{\frac{3}{4}})\) 的。
一种优化是（在能做的情况下）直接预处理 \(F(i)\) 到 \(n^{\frac{2}{3}}\)（一般来说 \(f\) 是积性函数，可以线性筛），然后对于小的直接引用，大的做上面的方法，可以证明复杂度是 \(O(n^{\frac{2}{3}})\) 的。
莫比乌斯函数
最常用的一集。
有经典式子 \(\varepsilon=\mu\ast I\)。而 \(\varepsilon\) 和 \(I\) 的前缀和都巨好求无比（\(\sum_{i=1}^n\varepsilon(i)=1,\sum_{i=1}^nI(i)=n\)）。于是可以直接算。
欧拉函数
怎么哪都是你们两个。
有经典式子 \(\varphi=id\ast \mu\)。故 \(id=\varphi \ast I\)，于是直接套板子。
其他函数
很随缘啊，取决于能不能构造出 \(g\)。
但是不要局限于筛。假如你能构造出 \(g,h\) 满足 \(f=g\ast h\)，而 \(g,h\) 都好求前缀和，其实可以直接用 \(\sum_{i=1}^n(f\ast g)(i)=\sum_{i=1}^ng(i)F(\left\lfloor\frac{n}{i}\right\rfloor)\) 直接数论分块算，复杂度还是 \(O(n^{\frac{1}{2}})\) 的。
模板题参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e7+5,inf=0x3f3f3f3f;
i64 n,mu[N],summu[N],phi[N],sumphi[N];
vector<i64> pri;
void init(i64 n){
mu[1]=1;phi[1]=1;
forup(i,2,n){
if(!phi[i]){
phi[i]=i-1;mu[i]=-1;
pri.push_back(i);
}
for(auto j:pri){
if(1ll*i*j>n) break;
if(i%j){
phi[i*j]=phi[i]*(j-1);
mu[i*j]=-mu[i];
}else{
phi[i*j]=phi[i]*j;
mu[i*j]=0;
break;
}
}
}
forup(i,1,n){
summu[i]=summu[i-1]+mu[i];
sumphi[i]=sumphi[i-1]+phi[i];
}
}
map<i64,pii> sum;
pii calc(i64 n){
if(n<=1e7){
return mkp(summu[n],sumphi[n]);
}
if(sum.count(n)) return sum[n];
i64 smu=1,sphi=1ll*(1+n)*n/2;
for(i64 l=2,r=0;l<=n;l=r+1){
r=n/(n/l);
pii res=calc(n/l);
smu-=(r-l+1)*res.fi;
sphi-=(r-l+1)*res.se;
}
smu/=1;sphi/=1;//象征性除以 1，防止复制板子的时候忘了。
sum[n]=mkp(smu,sphi);
return mkp(smu,sphi);
}
void solve(){
n=read();
pii res=calc(n);
printf("%lld %lld\n",res.se,res.fi);
}
signed main(){
init(1e7);
i64 t=read();
while(t--){
solve();
}
}
Powerful Number 筛（PN 筛）
PN 筛用于亚线性地求解一些积性函数的前缀和。
Powerful Number
Poweful Number，Number 中的 Number，数字中的数字，数字中的征服者，数字的王
若一个正整数 \(n=\prod p_i^{c_i}\)，\(\forall i\) 均有 \(c_i>1\)，则称 \(n\) 为一个 Powerful Number（注意 \(1\) 也满足这个条件）。
显然所有 PowerFul Number 都能写成 \(a^2b^3\)，考虑偶数就全放 \(a\) 里，奇数就拆三个放 \(b\) 里。
那么 \(n\) 以内的 Powerful Number1 个数就是 \(\sum_{a=1}^{\sqrt{n}}\sqrt[3]{\frac{n}{a^2}}\)。根据一些我不会的证明这玩意是 \(O(\sqrt{n})\) 级别的。
PN 筛
首先我们需要构造一个好求前缀和的积性函数 \(g\)，满足对于所有质数 \(p\le n\) 均有 \(g(p)=f(p)\)（非质数点位不作要求，比如若 \(f\) 在质数位置都取 \(1\) 时，\(g\) 可能可以取 \(I\)）。
考虑构造一个 \(h\ast g=f\)。根据狄利克雷卷积的性质，有 \(h(1)=1\) 且 \(h\) 也是积性函数。下面探讨一些 \(h\) 的性质。
对于任意质数 \(p\)，显然有 \(f(p)=h(p)g(1)+h(1)g(p)\)。由于 \(g(1)=h(1)=1\)（非 \(0\) 积性函数的性质），则 \(f(p)=h(p)+g(p)\)。又由于 \(g(p)=f(p)\)，所以 \(h(p)=0\)。而注意到 \(h\) 为积性函数，容易发现在非 Powerful Number 的位置均有 \(h(i)=0\)（否则就会带一个一次质因子，根据积性 \(h(i)=0\)）。
关于 \(h\) 的构造，因为它是积性函数，所以其实也只需要考虑 \(p^k\) 就行了。能求出 \(h\) 的通项公式当然好，但如果求不出来也有办法。考虑 \(f(p^k)=\sum_{i=0}^kh(p^i)g(p^{k-i})\)，所以 \(h(p^k)=f(p^k)-\sum_{i=0}^{k-1}h(p^i)g(p^{k-i})\)。又因为 \(O(\sqrt{n})\) 内指数数量约为 \(O(\frac{\sqrt{n}}{\log n})\) 级别的，素数的幂次上界是 \(\log n\) 的。所以直接暴力复杂度是 \(O(\frac{\sqrt{n}}{\log n}\log^2n)=O(\sqrt{n}\log n)\)，还是非常小的，而且这个上界显然非常松吧。另外空间复杂度是 \(O(\frac{\sqrt{n}}{\log n}\log n)=O(\sqrt{n})\) 的。当然如果能求出 \(h\) 的通项公式那么复杂度会低一点。
由于 \(F(n)=\sum_{i=1}^n(h\ast g)(i)=\sum_{i=1}^nh(i)G(\left\lfloor\frac{n}{i}\right\rfloor)\)，而 \(h\) 只在 PN 处有值。则大力搜索 \(i\)（枚举 \(\sqrt{n}\) 以内的质数再从 \(2\) 开始枚举其幂次）然后乘上 \(g\) 的前缀和即可。复杂度 \(O((p+q)\sqrt{n})\)，其中 \(p,q\) 分别是求 \(g\) 前缀和的复杂度和求 \(h\) 单点值的复杂度。
结语
感觉学了杜教筛和 PN 筛就差不多了啊。
这篇博客提到的筛法的核心是构造 \(g,h\) 函数（除了线性筛），这个就和做几何题一样，想到了就简单，没想到就暴毙，感觉很考验经验啊。