【模板】杜教筛

#include <stdio.h>
#include <math.h>
#include <map>
#define ull unsigned long long
#define llt long long int
#define uit unsigned int
const int N = 5e6+10;
int onlimits;
std :: map<uit,llt> Smu;
llt mu[N], premu[N];
llt get_Smu(uit k) {
	if(k <= onlimits) 
		return premu[k];
	if(Smu.find(k) != Smu.end()) 
		return Smu[k];
	llt res = 1LL;
	for(llt l = 2, r;l <= k;l = r+1) {
		r = k/(k/l);
		res -= (r-l+1)*get_Smu(k/l);
	}
	return Smu[k] = res;
}
std :: map<uit,ull> Sphi;
ull phi[N], prephi[N];
ull get_Sphi(uit k) {
	if(k <= onlimits) 
		return prephi[k];
	if(Sphi.find(k) != Sphi.end()) 
		return Sphi[k];
	ull res = 1LL*k*(k+1)/2LL;
	for(ull l = 2, r;l <= k;l = r+1) {
		r = k/(k/l);
		res -= (r-l+1)*get_Sphi(k/l);
	}
	return Sphi[k] = res;
}
int prime[N];
bool check[N];
void line() {
	phi[1] = mu[1] = 1;
	premu[1] = prephi[1] = 1;
	for(int i = 2;i <= onlimits;++i) {
		if(!check[i]) {
			prime[++prime[0]] = i;
			mu[i] = -1;
			phi[i] = i-1;
		}
		premu[i] = premu[i-1]+mu[i];
		prephi[i] = prephi[i-1]+phi[i];
		for(int j = 1;j <= prime[0];++j) {
			if(i*prime[j] > onlimits) 
				break;
			check[i*prime[j]] = true;
			if(i%prime[j] == 0) {
				mu[i*prime[j]] = 0;
				phi[i*prime[j]] = phi[i]*prime[j];
				break;
			}
			phi[i*prime[j]] = phi[i]*phi[prime[j]];
			mu[i*prime[j]] = -mu[i];
		}
	}
}
int n;
uit m;
signed main() {
	scanf("%d",&n);
	onlimits = 5000000;
	line();
	for(int i = 1;i <= n;++i) {
		scanf("%u",&m);
		printf("%llu %lld\n",get_Sphi(m),get_Smu(m));
	}
	return 0;
}