杜教筛模板

杜教筛

Source

题目(LuoguP4213)

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define xx first
#define yy second

using namespace std;

const int N = 5000000 + 5, M = 5000000;

int pri[N], tot, phi[N], mu[N];
ll sum_phi[N];
ll sum_mu[N];
bool vis[N];
map<int,ll> Phi;
map<int,ll> Mu;
inline void init ();
ll PHI (int u) {
	if (u <= M) {
		return sum_phi[u];
	}
	if (Phi[u]) {
		return Phi[u];
	}
	ll res = 0;
	for (register int l = 2, r; r < 2147483647 && l <= u; l = r + 1) {
		r = u / (u / l);
		res += 1ULL * (r - l + 1) * PHI (u / l);
	}
	return Phi[u] = (ull) u * (u + 1ll) / 2ll - res;
}
ll MU (int u) {
	if (u <= M) {
		return sum_mu[u];
	}
	if (Mu[u]) {
		return Mu[u];
	}
	ll res = 1LL;
	int l = 2, r;
	for (; l <= u && r < 2147483647; l = r + 1) {
		r = u / (u / l);
		res -= (r - l + 1) * MU (u / l);
	}
	return Mu[u] = res;
}
int main () {
	init ();
	for (int i = 1; i <= M; ++i) {
		sum_phi[i] = sum_phi[i - 1] + phi[i];
		sum_mu[i] = sum_mu[i - 1] + mu[i];
	}
	int t;
	scanf ("%d", &t);
	while (t--) {
		int x;
		scanf ("%d", &x);
		printf ("%lld %lld
", PHI (x), MU (x));
	}
	return 0;
}

inline void init () {
	phi[1] = 1;
	mu[1] = 1;
	for (int i = 2; i <= M; ++i) {
		if (!vis[i]) {
			pri[++tot] = i;
			mu[i] = -1;
			phi[i] = i - 1;
		}
		for (int j = 1; j <= tot; ++j) {
			if (pri[j] * i > M) {
				break;
			}
			vis[i * pri[j]] = 1;
			if (i % pri[j] == 0) {
				phi[i * pri[j]] = phi[i] * pri[j];
				mu[i * pri[j]] = 0;
				break;
			}
			else {
				phi[i * pri[j]] = phi[i] * (pri[j] - 1);
				mu[i * pri[j]] = -mu[i];
			}
		}
	}
}

Note

卡的好啊。

各种地方都要注意(Long Long)的使用。