luoguP4213 【模闆】杜教篩（Sum）杜教篩

連結

luogu

思路

為了做hdu來學杜教篩。

杜教篩模闆題。

卡常數，我加了register居然跑到不到800ms。

太深了。

代碼

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int _=5000030;
int vis[_],pri[_],cnt,N,limit,mu[_];
ll phi[_];
unordered_map<int,ll> ans_phi;
unordered_map<int,ll> ans_mu;
inline void Euler() {
	vis[1]=phi[1]=mu[1]=1;
	for(register int i=1;i<=limit;++i) {
		if(!vis[i]) pri[++cnt]=i,mu[i]=-1,phi[i]=i-1;
		for(register int j=1;j<=cnt&&i*pri[j]<=limit;++j) {
			vis[i*pri[j]]=1;
			if(i%pri[j]==0) {
				mu[i*pri[j]]=0;
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			} else {
				mu[i*pri[j]]=-mu[i];
				phi[i*pri[j]]=phi[i]*(pri[j]-1);
			}
		}
	}
	for(register int i=2;i<=limit;++i) mu[i]+=mu[i-1],phi[i]+=phi[i-1];
}
ll Solvephi(register int n) {
	if(n<=limit) return phi[n];
	if(ans_phi[n]) return ans_phi[n];
	register ll tmp=1LL*n*(n+1)/2;
	for(register int l=2,r;l<=n;l=r+1)
		r=n/(n/l),tmp-=Solvephi(n/l)*(r-l+1);
	return ans_phi[n]=tmp;
}
ll Solvemu(register int n) {
	if(n<=limit) return mu[n];	
	if(ans_mu[n]) return ans_mu[n];
	register ll tmp=1;
	for(register int l=2,r;l<=n;l=r+1)
		r=n/(n/l),tmp-=Solvemu(n/l)*(r-l+1);
	return ans_mu[n]=tmp;
}
int main() {
	int T;cin>>T;
	limit=5000000;
	Euler();
	while(T --> 0) {
		cin>>N;
		printf("%lld %lld\n",Solvephi(N),Solvemu(N));
	}
	return 0;
}