杜教筛

参考资料

• 杜教筛 - OI Wiki

例题

洛谷 P4213 【模板】杜教筛

洛谷 P4213 【模板】杜教筛

给定 $T$ 个正整数 $n$，求 $\sum_{i=1}^n\varphi(i)$ 和 $\sum_{i=1}^n \mu(i)$。（$T\le10,n\le2^{31}$）

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=5000005;
bool vis[N];
ll prime[N],phi[N],mu[N];
unordered_map<ll,ll> sum_phi,sum_mu;
void init()
{
	vis[0]=vis[1]=1;
	phi[1]=mu[1]=1;
	int cnt=0;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		{
			prime[++cnt]=i;
			phi[i]=i-1;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(i*prime[j]>=N)break;
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				mu[i*prime[j]]=0;
				break;
			}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
			mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<N;i++)
	{
		phi[i]+=phi[i-1];
		mu[i]+=mu[i-1];
	}
}
ll sum_g(ll x)
{
	return x;
}
ll get_phi(ll x)
{
	if(x<N)return phi[x];
	if(sum_phi[x])return sum_phi[x];
	ll ans=x*(x+1)/2;
	for(ll l=2,r;l<=x;l=r+1)
	{
		r=x/(x/l);
		ans-=(sum_g(r)-sum_g(l-1))*get_phi(x/l);
	}
	return sum_phi[x]=ans/sum_g(1);
}
ll get_mu(ll x)
{
	if(x<N)return mu[x];
	if(sum_mu[x])return sum_mu[x];
	ll ans=1;
	for(ll l=2,r;l<=x;l=r+1)
	{
		r=x/(x/l);
		ans-=(sum_g(r)-sum_g(l-1))*get_mu(x/l);
	}
	return sum_mu[x]=ans/sum_g(1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	init();
	int T;
	cin>>T;
	while(T--)
	{
		ll n;
		cin>>n;
		cout<<get_phi(n)<<' '<<get_mu(n)<<'\n';
	}
	return 0;
}