杜教筛

一句话总结杜教筛：

综合起来，杜教筛算法可以概况为：用狄利克雷卷积构造递推式，编程时用整除分块和线性筛优化，算法复杂度达到了$O(n^{\frac{2}{3}})$。

只要给你的函数的卷积和函数可以方便的表示出来且好计算，那么杜教筛就有用武之地。

现在开始推倒杜教筛的过程

要求函数：$f(x)$的前缀和 $s(x)$

我们设两个函数为$h(x) g(x)$有$h(x)=f(x)*g(x)$

$\sum_{i=1}^nh(x)=\sum_{i=1}^n\sum_{j|i}f(\frac{i}{j})g(j)$

$\sum_{i=1}^nh(x)=\sum_{j=1}^n\sum_{j|i}^nf(\frac{i}{j})g(j)$

设k=i/j

$\sum_{i=1}^nh(x)=\sum_{j=1}^ng(j)\sum_{k=1}^{\frac{n}{j}}f(k)$

$\sum_{i=1}^nh(x)=\sum_{j=1}^ng(j)s(\frac{n}{j})$

把我们目标$s(n)$分离出来

$s(n)g(1)=\sum_{i=1}^nh(i)-\sum_{j=2}^ns(\lfloor\frac{n}{j}\rfloor )g(j)$

真就这么魔幻的算出来了。

这是一个递归计算的式子，大佬告诉我们其时间复杂度为$O(n^{\frac{2}{3}})$(前提$h(i),g(i)$足够简单易求

---

基础推导1

• $\phi$函数的前缀和

首先关于$\phi$函数

$n=\phi * 1$

证明，$\frac{1}{n},\frac{2}{n},\frac{3}{n},\frac{4}{n},\frac{5}{n}, ......\frac{n}{n}$化简，每一个分母显然都是n的因数，且每个分母为y的分子都有$\phi(y)$个，所以相加为$n$。

---

然后我们发现将这个式子套在杜教筛上，g函数和h函数都十分简单易求。

将g函数和h函数带入

$s(n)=\frac{n*(1+n)}{2}-\sum_{j=2}^ns(\lfloor\frac{n}{j}\rfloor )$

记忆化递归求解即可。

基础推导2

• $\mu$函数的前后和

有

$E=\mu*1$

不会左转莫比乌斯反演

然后又可以愉快的套杜教筛

$s(n)=1-\sum_{j=2}^ns(\lfloor\frac{n}{j}\rfloor )$

记忆化递归求解即可。

---

板题1 $\mu$与$\phi$的前缀和

思路：没有思路，就是板子

code

#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
#define int long long
const int M=5e6;
int n,pri[M+5],cntp,phi[M+5],mu[M+5],vis[M+5];
tr1::unordered_map <int,int> sphi,smu;

//筛一部分的前缀和，使时间复杂度更优

void pre(){
	phi[1]=1;mu[1]=1;
	for(int i=2;i<=M;i++){
		if(!vis[i]){
			pri[++cntp]=i;mu[i]=-1;phi[i]=i-1;
		}
		for(int j=1;j<=cntp&&pri[j]*i<=M;j++){
		    vis[i*pri[j]]=1;
			if(i%pri[j]!=0){
				mu[i*pri[j]]=mu[i]*-1;phi[i*pri[j]]=phi[i]*phi[pri[j]];
			}
			else{
				mu[i*pri[j]]=0;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];
}

int getsumphi(int x){
	if(x<=M) return phi[x];
	if(sphi[x]) return sphi[x];
	int res=x*(x+1)/2;
	for(int S=2,E;S<=x;S=E+1){
		E=x/(x/S);
		res-=getsumphi(x/S)*(E-S+1);
	}
	sphi[x]=res;return res;
}

int getsummu(int x){
	if(x<=M) return mu[x];
	if(smu[x]) return smu[x];
	int res=1;
	for(int S=2,E;S<=x;S=E+1){
		E=x/(x/S);
		res-=getsummu(x/S)*(E-S+1);
	}
	smu[x]=res;return res;
}

signed main(){
	pre();
	int T;cin>>T;
	while(T--){
		cin>>n;cout<<getsumphi(n)<<" "<<getsummu(n)<<"\n";
	}
	return 0;
}