脚本宝典收集整理的这篇文章主要介绍了【洛谷 P4213】 【模板】杜教筛（Sum），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

#include <bITs/stdc++.h>
using namespace std;
#define ll long long 
int cnt, n;
map<int, long long> mpu, mpphi;
int PRime[10000010], mu[10000010], v[10000010], usum[10000010], phi[10000010];
ll phisum[10000010];
ll getusum(int n){
	if(n <= 10000000) return usum[n];
	if(mpu[n]) return mpu[n];
	ll ans = 1;
	for(ll l = 2, r = 0; l <= n; l = r + 1){
		r = n / (n / l);
		ans -= (r-l+1) * getusum(n / l);
	}
	return mpu[n] = ans;
}
ll getphisum(int n){
	if(n <= 10000000) return phisum[n];
	if(mpphi[n]) return mpphi[n];
	ll ans = (ll)n * ((ll)n+1) / 2;
	for(ll l = 2, r = 0; l <= n; l = r + 1){
		r = n / (n / l);
		ans -= (r-l+1) * getphisum(n / l);
	}
	return mpphi[n] = ans;
}
int T;
int main(){
	mu[1] = phi[1] = usum[1] = phisum[1] = 1; 
	for(int i = 2; i <= 10000000; ++i){
		if(!v[i]){ mu[i] = -1; phi[i] = i-1; prime[++cnt] = i; }
		usum[i] = usum[i-1] + mu[i];
		phisum[i] = phisum[i-1] + phi[i];
		for(int j = 1; j <= cnt && (ll)i * prime[j] <= 10000000; ++j){
			v[i * prime[j]] = 1;
			if(i % prime[j] == 0){
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			mu[i * prime[j]] = -mu[i];
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
	scanf("%d", &amp;T);
	while(T--){
		mpu.clear(); mpphi.clear();
		scanf("%d", &n);
		printf("%lld %lldn", getphisum(n), getusum(n));
	}
}

脚本宝典总结

以上是脚本宝典为你收集整理的【洛谷 P4213】 【模板】杜教筛（Sum）全部内容，希望文章能够帮你解决【洛谷 P4213】 【模板】杜教筛（Sum）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。