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;

}