杜教筛学习笔记

前置知识：莫比乌斯反演+狄利克雷卷积

现在要求一个积性函数 \(f(x)\) 的前缀和，设 \(\sum_{i=1}^n f(i)=S(n)\)

再找一个积性函数 \(g\)，他们狄利克雷卷积的前缀和就是：

\[\begin{aligned}&\sum_{i=1}^{n}(f*g)(i)\\&=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})\\&=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\\&=\sum_{d=1}^ng(d)s(\lfloor\frac{n}{d}\rfloor)\end{aligned} \]

接着看 \(g(1)s(n)\) 等于什么，可以看作是做差的结果，即：

\[\sum_{i=1}^ng(i)s(\lfloor\frac{n}{i}\rfloor)-\sum_{i=2}^ng(i)s(\lfloor\frac{n}{i}\rfloor) \]

根据前面的推导，前面的部分就是 \(\sum_{i=1}^{n}(f*g)(i)\)

就有：\(g(1)s(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^ng(i)s(\lfloor\frac{n}{i}\rfloor)\)

所以如果有一个较好的 \(g\) 函数时，就能较快的求出 \(\sum_{i=1}^{n}(f*g)(i)\) 和 \(g\) 的前缀和，并整除分块求解

例题：【模板】杜教筛

https://www.gxyzoj.com/d/gxyznoi/p/63

根据结论 \(\mu*1=\varepsilon\)，所以第一问 \(f=\mu,g=1,f*g=\varepsilon\)

根据结论 \(\varphi*1=id\)，所以第二问 \(f=\varphi,g=1,f*g=id\)

最后递归求解即可

点击查看代码

#include<cstdio>
#include<map>
#define ll long long
using namespace std;
const int N=5000000;
int T,vis[N+5],mu[N+5],p[N+5],cnt,phi[N+5];
ll n,s_mu[N+5],s_phi[N+5];
void init()
{
	phi[1]=mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!vis[i])
		{
			p[++cnt]=i,mu[i]=-1,phi[i]=i-1;
		}
		for(int j=1;p[j]*i<=N&&j<=cnt;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)
			{
				phi[i*p[j]]=p[j]*phi[i];
				break;
			}
			phi[i*p[j]]=phi[i]*phi[p[j]];
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++)
	{
		s_mu[i]=s_mu[i-1]+mu[i];
		s_phi[i]=s_phi[i-1]+phi[i];
	}
}
map<ll,ll> f_mu,f_phi;
ll getmu(ll n)
{
	if(n<=N) return s_mu[n];
	if(f_mu.count(n)) return f_mu[n];
	ll res=1;
	for(ll i=2;i<=n;i++)
	{
		ll j=n/(n/i);
		res-=(j-i+1)*getmu(n/i);
		i=j;
	}
	f_mu[n]=res;
	return res;
}
ll getphi(ll n)
{
	if(n<=N) return s_phi[n];
	if(f_phi.count(n)) return f_phi[n];
	ll res=1ll*n*(n+1ll)/2ll;
	for(ll i=2;i<=n;i++)
	{
		ll j=n/(n/i);
		res-=(j-i+1)*getphi(n/i);
		i=j;
	}
	f_phi[n]=res;
	return res;
}
int main()
{
	scanf("%d",&T);
	init();
	while(T--)
	{
		scanf("%lld",&n);
		printf("%lld %lld\n",getphi(n),getmu(n));
	}
	return 0;
}