0. 前言——什么是杜教筛？
杜教筛是一种能在低于线性的时间复杂度内求出积性函数的前缀和。一般用来求 \(\mu(i)\) 或 \(\varphi(i)\) 的前缀和。
那么杜教筛有哪些用处呢？就拿一个我们再熟悉不过的问题。
求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(i,j),n \leq 10^5\)。
一眼出解法。
该解法是 \(\mathcal O(n \times d(n))\) 的，在大多数人看了已经足够优秀了。但总不免有毒瘤出题人故意把数据加强到 \(10^{10}\)，纯粹为了考察你会不会杜教筛、min_25筛等高级筛法。这时候就需要杜教筛了。
1. 前置知识
学会杜教筛这种神仙玩意儿需要你有牢固的数论基础。所以在进入正题之前，我们也需回顾一些以前学过的数论技巧。
数论函数与积性函数
数论函数的定义非常广泛，但是我们也不必深究其定义，我们只需知道，数论中常见的 \(\mu(x),\varphi(x)\) 都属于数论函数。
知道了数论函数，想必你一定也听说过一类函数叫做积性函数。它的定义是：如果数论 \(f(x)\) 满足 \(f(1)=1\)，并且满足对于所有 \(\gcd(a,b)=1\)，都有 \(f(ab)=f(a)f(b)\)，那么 \(f(x)\) 就是积性函数。
特殊之中还有特殊。在积性函数的基础上，如果对于任意 \(a,b\) 也都有 \(f(ab)=f(a)f(b)\)，那么 \(f(x)\) 就被称为“完全积性函数”。
而杜教筛，就是专门与这积性函数打交道的算法。
先举几个典型的积性函数吧：
- \(\varphi(x)\)，欧拉函数，即 \([1,x]\) 中与 \(x\) 互质的数的个数。
- \(\mu(x)\)，莫比乌斯函数。
- \(d(x)\)，约数个数函数。
- \(\sigma(x)\)，约数和函数。
还有以下几个完全积性函数：
- \(\epsilon(x)\)，学名曰“原函数”，说白了 \(\epsilon(x)\) 就等于 \([x=1]\)。
- \(I(x)\)，恒等函数。\(I(x)=1\)。
- \(id(x)\)，单位函数。\(id(x)=x\)。
在杜教筛中，比较常见的 \(\varphi(x),\mu(x),\epsilon(x),I(x),id(x)\)。
它们的性质将在下文中相信分析。
狄利克雷卷积
假设有两个数论函数 \(f,g\)，那么它们的狄利克雷卷积 \(h=f*g\) 满足 \(h(x)=\sum\limits_{d|x}f(d)*g(\frac{x}{d})\)。
和普通乘法一样，狄利克雷卷积也具有交换律、结合律、分配律。
这三个性质证明都比较容易，这里也不再赘述了。
狄利克雷卷积的定义就这么多。那么这狄利克雷卷积有何用途呢？这就要与我们之前几个积性函数结合了。
莫比乌斯函数
这……两天前刚学的不至于这么快就忘了吧。
here
莫比乌斯函数最重要的函数就是 \(\sum\limits_{d|n}\mu(d)=[n=1]\)
咦？怎么看起来有点儿眼熟？
这 \([n=1]\) 不就是 \(\epsilon(n)\) 吗？
于是我们有 \(\sum\limits_{d|n}\mu(d)\times I(\frac{n}{d})=\epsilon(n)\)。
用狄利克雷卷积的形式写出来就是 \(\mu\times I=\epsilon\)。
莫比乌斯函数还有一个特别重要的性质，那就是：
假如 \(F(x)=\sum\limits_{d|x}f(d)\)，那么 \(f(x)=\sum\limits_{d|x}\mu(d)F(\frac{n}{d})\)。
其实 5 天前我就埋下了伏笔。当时我们使用纯式子的方法证明了这个定理，现在我们再从狄利克雷卷积的角度看这个问题。
原式等价于已知 \(F=f \times I\)，证明 \(f=F \times \mu\)
将两边同时卷上 \(\mu\)，得到 \(F \times \mu = f \times I \times \mu\)
根据前面的推论 \(I \times \mu\) 就是 \(\epsilon\)。
于是 \(F \times \mu=f \times \epsilon\)。
而 \(f \times \epsilon\) 就等于 \(f\)（也很好理解，随便带一下就出来了）
故 \(F \times \mu=f\)
欧拉函数
这玩意儿是我 3 个月前学的。由于当时我比较懒没有写博客，所以现在只好重新推一遍啦。
首先欧拉函数有一个特别著名的式子 \(\sum\limits_{d|n}\varphi(d)=n\)。
为什么？考虑 \([1,n]\) 中的某个数 \(x\)。
显然 \(\frac{n}{\gcd(n,x)}\) 与 \(\frac{x}{\gcd(n,x)}\) 互质。
而 \(n>x\)，所以 \(\frac{x}{\gcd(n,x)}\) 会对 \(\varphi(\frac{n}{\gcd(n,x)})\) 产生贡献。
这样我们就可以表示出 \([1,n]\) 的所有数。故 \(\sum\limits_{d|n}\varphi(d)=n\)。
我们还是使用狄利克雷卷积的角度看这个式子。
那么有 \(\varphi \times I=id\)，又一个重要的式子。
杜教筛
终于进入正轨了。可以说，我前面那么多内容都是为了这十来行左右的内容做铺垫的。
我们要求积性函数 \(f(i)\) 的前缀和。记 \(s(n)\sum\limits_{i=1}^nf(i)\)。
假设有积性函数 \(f'(i),g(i)\) 满足 \(f \times f'=g\)
那么显然 \(\sum\limits_{i=1}^ng(i)=\sum\limits_{x=1}^n\sum\limits_{d|x}f(d) \times f'(\frac{x}{d})\)。
即 \(\sum\limits_{i=1}^ng(i)=\sum\limits_{ij \leq n}f(i) \times f'(j)\)
即 \(\sum\limits_{i=1}^ng(i)=\sum\limits_{i=1}^nf'(i) \times s(\lfloor\frac{n}{i}\rfloor)\)
把第一项提取出来，\(\sum\limits_{i=1}^ng(i)=f'(1)s(n)+\sum\limits_{i=2}^nf'(i) \times s(\lfloor\frac{n}{i}\rfloor)\)。
由于 \(f'(1)=1\)，故 \(s(n)=\sum\limits_{i=1}^ng(i)-\sum\limits_{i=2}^nf'(i) \times s(\lfloor\frac{n}{i}\rfloor)\)。
后面那堆东西显然可以整除分块+递归求。现在我们的任务就是找出两个积性函数 \(f',g\)，它们的前缀和可以在短时间内求出来。
杜教筛的核心内容差不多就到此为止。具体情况具体分析吧。
1. 求 \(\mu(x)\) 的前缀和。
根据 \(\mu \times I=\epsilon\)，我们取 \(f'=I,g=\epsilon\)。
\(I\) 的前缀和 \(\sum\limits_{i=1}^nI(i)=n\)，\(\epsilon\) 的前缀和 \(\sum\limits_{i=1}^n\epsilon(i)=1\)。
把它们带进上面那个式子就可以了。
2. 求 \(\varphi(x)\) 的前缀和。
和上面几乎一模一样。
只不过这里我们取 \(f'=I,g=id\)。
3. 求 \(f(x)=x \times \varphi(x)\) 的前缀和。
其实还是那个套路啊。。。。。。
很明显 \(f(x)\) 是积性函数。
我们尝试构造出合适的 \(f'(x)\)。
根据上面的推论 \(g(x)=\sum\limits_{d|x}d\times\varphi(d)f'(\frac{x}{d})\)。
我们想把这里的 \(f\) 消掉，那么我们尝试 \(f'=id\)。
那么 \(g(x)=\sum\limits_{d|x}d\times\varphi(d)f'(\frac{x}{d})=x\sum\limits_{d|x}\varphi(d)=x^2\)。
欸，这 \(g(x)\) 长得挺简洁的，并且前缀和也很好算。
把它们统统带进杜教筛的式子就可以了。
2. 实现
杜教筛的大致思想与简单应用到此为止。
可论实现，杜教筛还有不少需注意的地方：
- 如果暴力求很容易 TLE。通过微积分可以算出暴力求是 \(\mathcal O(n^{\frac{3}{4}})\) 的。而如果我们提前预处理比较小的 \(s(i)\)，就可以使得复杂度降下去。这里建议预处理到 \(\mathcal O(n^{\frac{2}{3}})\)。
- 要使用记忆化搜索。这里建议使用
unordered_map代替map，复杂度可以少一个 \(\log\)。
最后给出代码（洛谷 P4213）：
/*
Contest: -
Problem: P4213
Author: tzc_wk
Time: 2020.9.3
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a) a.begin(),a.end()
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,0x3f,sizeof(a))
#define y1 y1010101010101
#define y0 y0101010101010
typedef pair<int,int> pii;
typedef long long ll;
inline int read(){
int x=0,neg=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') neg=-1;
c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*neg;
}
bool vis[10000005];
ll mu[10000005],phi[10000005],pri[5000005],pcnt=0;
inline void prework(){
phi[1]=1;mu[1]=1;
for(int i=2;i<=10000000;i++){
if(!vis[i]){mu[i]=-1;phi[i]=i-1;pri[++pcnt]=i;}
for(int j=1;j<=pcnt&&pri[j]*i<=10000000;j++){
vis[i*pri[j]]=1;
if(i%pri[j]==0){phi[pri[j]*i]=phi[i]*pri[j];break;}
else mu[pri[j]*i]=-mu[i],phi[pri[j]*i]=phi[pri[j]]*phi[i];
}
}
for(int i=2;i<=10000000;i++) mu[i]+=mu[i-1],phi[i]+=phi[i-1];
}
unordered_map<ll,ll> phis;
unordered_map<ll,ll> mus;
inline ll getphi(ll x){
if(x<=10000000) return phi[x];
if(phis[x]) return phis[x];
ll ans=1ll*x*(x+1ll)/2ll;
for(ll l=2,r;l<=x;l=r+1){
r=x/(x/l);
ans-=getphi(x/l)*(r-l+1);
}
return phis[x]=ans;
}
inline ll getmu(ll x){
if(x<=10000000) return mu[x];
if(mus[x]) return mus[x];
ll ans=1;
for(ll l=2,r;l<=x;l=r+1){
r=x/(x/l);
ans-=getmu(x/l)*(r-l+1);
}
return mus[x]=ans;
}
int main(){
prework();int T=read();
while(T--){
ll n=read();
printf("%lld %lld\n",getphi(n),getmu(n));
}
return 0;
}