杜教筛

目的：对于一个积性函数 $\operatorname{f}$，我们要对它求前缀和，但是数据范围较大（$10^{10}$），不支持 $\varTheta(n)$，这时，我们就可以使用杜教筛。

$$\operatorname{S}(n)=\sum_{i=1}{n}\operatorname{f}(i) \\ \operatorname{g}(1)\operatorname{S}(n)=\sum_{i=1}^n(\operatorname{f}*\operatorname{g})(i)-\sum_{i=2}^n\operatorname{g}(i)\operatorname{S}(\lfloor\frac{n}{i}\rfloor)$$

其中，$\operatorname{g}$ 是我们自己设的函数，经常为 $\operatorname{id},\operatorname{1},\varepsilon$ 等，它们的 $\operatorname{g}(1)=1$，所以常可忽略。

给一个求 $\varphi$ 的板子。

using ll = long long;
constexpr int N = 1e6;
ll sphi[N + 10];
unordered_mapSphi;
inline ll Sumphi(int n) {
	if (n <= N) return sphi[n];
	if (Sphi[n]) return Sphi[n];
	ll ret = 1ll * n * (n + 1) / 2;
	for (int l = 2, r; l <= n; l = r + 1)
		r = n / (n / l),
		ret -= (r - l + 1) * Sumphi(n / l);
	return Sphi[n] = ret;
}
vectorprm;
bool vis[N + 10];
ll phi[N + 10];
void iniit() {
	sphi[1] = phi[1] = 1;
	for (int i = 2; i <= N; i++) {
		if (!vis[i]) {
			prm.push_back(i);
			phi[i] = i - 1;
		}
		for (int& v : prm) {
			if (i * v > N) break;
			vis[i * v] = true;
			if (i % v == 0) {
				phi[i * v] = phi[i] * v;
				break;
			}
			phi[i * v] = phi[i] * phi[v];
		}
		sphi[i] = sphi[i - 1] + phi[i];
	}
}

大致板子长这样。

ll GetSum(int n) {
	ll ans = f_g_sum(n);
	for (ll l = 2, r; l <= n; l = r + 1)
		r = (n / (n / l)),
		ans -= (g_sum(r) - g_sum(l - 1)) * GetSum(n / l);
	return ans;
}