杜教筛是一种能用低于线性时间复杂度的方法计算积性函数前缀和的算法。
算法描述
我们要求一个函数 \(f\) 的前缀和：
$$S(n)=\sum_{i=1}^n f(i)$$
最原始的方法当然是用线性筛把 \(1 \sim n\) 的所有 \(f(i)\) 值求出来，再相加。时间复杂度 \(O(n)\)。
能不能更快一些呢？
我们找一个积性函数 \(g\)，求一下 \(f*g\) 的前缀和。
$$\begin{align*} \sum_{i=1}^n (f*g)(i) =&\sum_{i=1}^n\sum_{d|i} f(d)g(\frac{i}{d}) \\ =&\sum_{d=1}^n g(d)\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}f(i)\\ =&\sum_{d=1}^n g(d)S(\left \lfloor \frac{n}{d} \right \rfloor) \end{align*} $$
现在求一下 \(g(1)S(n)\) 的值，容易发现：
$$ \begin{align*} g(1)S(n) =& \sum_{i=1}^n g(i)S(\left \lfloor \frac{n}{i} \right \rfloor)-\sum_{i=2}^n g(i)S(\left \lfloor \frac{n}{i} \right \rfloor)\\ =& \sum_{i=1}^n (f*g)(i)-\sum_{i=2}^n g(i)S(\left \lfloor \frac{n}{i} \right \rfloor) \end{align*} $$
前半部分是个前缀和，后半部分数论分块后可以递归来计算。
可以证明，这么做的时间复杂度是 \(O(n^{\frac{3}{4}})\) 的。
如果我们预先用线性筛筛出前 \(O(n^{\frac{2}{3}})\) 个数的 \(f\) 值，可以将时间复杂度优化到 \(O(n^{\frac{2}{3}})\)。
（上面时间复杂度的证明之后再填坑）
为了加快效率，可以用记忆化搜索的方式存储已经算过的值。
现在唯一的问题就是对于一个 \(f\)，找到一个合适的 \(g\)，这个 \(g\) 要满足 \(g\) 和 \(f*g\) 的前缀和都比较好算。
几个例子
\(\mu\) 的前缀和
因为 \(\mu * 1=\epsilon\)，从而有 \(f=\mu\)，\(g=1\)，\(f*g=\epsilon\)。
long long mu_sum(long long x)
{
if(x<=MAXN)return mu[x];//已经筛过的部分
if(muans.count(x))return muans[x];//记忆化搜索
long long ans=1;//前半部分的和
for(long long l=2,r;l<=x;l=r+1)//数论分块算后半部分
{
r=x/(x/l);
ans-=(r-l+1)*mu_sum(x/l);
}
return muans[x]=ans;
}
\(\varphi\) 的前缀和
因为 \(\varphi * 1=\text{id}\)，从而有 \(f=\varphi\)，\(g=1\)，\(f*g=\text{id}\)。
long long phi_sum(long long x)
{
if(x<=MAXN)return phi[x];
if(phians.count(x))return phians[x];
long long ans=x*(x+1)/2;
for(long long l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1)*phi_sum(x/l);
}
return phians[x]=ans;
}