[洛谷P4213]【模板】杜教筛（Sum）

题目大意：给你$n$，求：
$$
\sum\limits_{i=1}^n\varphi(i),\sum\limits_{i=1}^n\mu(i)
$$
最多$10$组数据，$n\leqslant2^{31}-1$

题解：杜教筛，用来求$\sum\limits_{i=1}^nf(i)$的，其中$f$是某个特殊函数。

若我们可以找到一个函数$g$，使得$g,f*g$两个函数的前缀和十分好算（$g*f$表示$g$和$f$的狄利克雷卷积），就可在$O(n^{\frac 23})$的复杂度内求出我们要的东西。令$S(n)=\sum\limits_{i=1}^nf(i)$
$$
\begin{align*}
\sum\limits_{i=1}^n(g*f)(i)&=\sum\limits_{i=1}^n\sum\limits_{d|i}g(d)f\left(\dfrac id\right)\\
&=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1,d|i}^nf\left(\dfrac id\right)\\
&=\sum\limits_{d=1}g(d)S\left(\left\lfloor\dfrac nd\right\rfloor\right)
\end{align*}\\
g(1)S(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)S\left(\left\lfloor\dfrac ni\right\rfloor\right)
$$
然后线性筛求出前$n^{\frac23}$项，剩余的递归+整除分块计算，需要记忆化。

$$
\sum\limits_{i=1}^n\varphi(i)：\\
\because\varphi*I=id\\
\therefore S(n)=\frac{n(n+1)}{2}-\sum_{i=2}^nS\left(\left\lfloor\dfrac n i\right\rfloor\right)
$$
$$
\sum\limits_{i=1}^n\mu(i)：\\
\because\mu*I=1\\
\therefore S(n)=1-\sum_{i=2}^nS\left(\left\lfloor\frac n i\right\rfloor\right)
$$

注意这道题中$n\leqslant2^{31}-1$，$+1$后会爆$int$，所以整除分块的时候要用$unsigned$

卡点：无

C++ Code：

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <unordered_map>

const int R = 1 << 22 | 1;

int plist[R >> 3], ptot;

bool notp[R];

long long phi[R], mu[R];

void sieve() {

	phi[1] = mu[1] = 1;

	for (int i = 2; i < R; ++i){

		if (!notp[i]) plist[ptot++]=i, phi[i] = i - 1, mu[i] = -1;

		for(int j = 0, t; (t = i * plist[j]) < R; ++j){

			notp[t] = true;

			if(i % plist[j] == 0) {

				phi[t] = phi[i] * plist[j];

				mu[t] = 0;

				break; }

			phi[t] = phi[i] * phi[plist[j]];

			mu[t] = -mu[i];

		}

	}

	for (int i = 2; i < R; ++i) phi[i] += phi[i - 1], mu[i] += mu[i - 1];

}

std::unordered_map<unsigned, long long> Phi, Mu;

long long sphi(unsigned n) {

	if (n < R) return phi[n];

	if (Phi.count(n)) return Phi[n];

	long long &t = Phi[n];

	for (unsigned l = 2, r; l <= n; l = r + 1) {

		r = n / (n / l);

		t += (r - l + 1) * sphi(n / l);

	}

	return t = static_cast<long long> (n + 1) * n / 2 - t;

}

long long smu(unsigned n) {

	if (n < R) return mu[n];

	if (Mu.count(n)) return Mu[n];

	long long &t = Mu[n];

	for (unsigned l = 2, r; l <= n; l = r + 1) {

		r = n / (n / l);

		t += (r - l + 1) * smu(n / l);

	}

	return t = 1 - t;

}

int T;

int main() {

	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cin.tie(0);

	sieve();

	std::cin >> T;

	while (T --> 0) {

		static unsigned n;

		std::cin >> n;

		std::cout << sphi(n) << ' ' << smu(n) << '\n';

	}

	return 0;

}

巴特西

[洛谷P4213]【模板】杜教筛（Sum）

最新文章

热门文章