杜教筛

前置相关

• 类型积性函数（注：以下皆为完全积性函数，即无需满足 $x \perp y$ 即有 $f(x) · f(y) = f(xy)$

  $\epsilon (n) = [n = 1]$

  $id (n) = n$

• 狄利克雷卷积与莫比乌斯函数

• 狄利克雷卷积与欧拉函数

  此处若以 $id $ 作单位元，则 $1$ 为 $\phi$ 的逆，即 $\phi * 1 = id$

  证明：由 $\sum\limits_{d | n} \phi (d) = n$ ，再带回原式可证

• 莫比乌斯函数与欧拉函数的转化
  $$
  \begin{aligned} \phi * 1 &= id \ \phi * 1 * \mu &= id * \mu \ \phi * \epsilon &= id * \mu \ \phi &= \sum\limits_{d | n} \mu(d) \frac{n}{d} \ \frac{\phi}{n} &= \sum\limits_{d | n} \frac{\mu(d)}{d} \end{aligned}
  $$

杜教筛

• 杜教筛用于求解积性函数前缀和一类问题

• 下面求解积性函数 $f$ 的前缀和

• 设积性函数 $f, g, h$ ，且 $h = f * g$ ，则有

$$
\begin{aligned} \sum\limits_{i = 1}^n h(n) &= \sum\limits_{i = 1}^n \sum\limits_{d | n} g(d)f(\frac{n}{d}) \\ &= \sum\limits_{d = 1}^n g(d) \sum\limits_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} f(i) \end{aligned}
$$

• 令 $S(n) = \sum\limits_{i = 1}^n f(i)$
• 将 $d = 1$ 时的提出，再移项，得

$$
S(n) = \sum\limits_{i = 1}^n h(i) - \sum\limits_{d = 2}^n g(d)S(\left\lfloor\frac{n}{d}\right\rfloor)
$$

• 那么预处理 $h, g$ 的前缀和（一般预处理 $n^{\frac{2}{3}}$ 个？），再递归整除分块即可处理，不过一般 $h, g$ 需要自己配
• 但实际上并不需要用 $\text{unordered_map}$ 来记忆化，设题目给定 $N$，当前递归到 $n$，则 $n$ 的答案可以被 $N / n$ 记录，也就是用 $visit(\lfloor\frac{N}n\rfloor)$ 来判断是否已被搜过，下面给出别人的简单证明为什么不会判重
• 

例

求$\sum\limits_{i = 1}^n \mu(i), \sum\limits_{i = 1}^n \phi(i)$

由 $\mu * 1 = \epsilon$ ，可令 $g = 1, h = \epsilon$ ，那么得到
$$
S(n) = 1 - \sum\limits_{d = 2}^n S(\left\lfloor\frac{n}{d}\right\rfloor)
$$
求 $\sum \phi$ 同理

求$\sum\limits_{i = 1}^n i \phi(i) （需要用配的）$

$$
h(n) = \sum\limits_{d | n} d \phi(d) g(\frac{n}{d})
$$

希望将 $d$ 消去，故配 $g = id$ ，得 $h(n) = n^2$
$$
S(n) = \sum\limits_{i = 1}^n i - \sum\limits_{d = 2}^n d S(\left\lfloor\frac{n}{d}\right\rfloor)
$$
即可解

代码（求解$\sum \mu, \sum \phi$ ）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <tr1/unordered_map>

using namespace std;

typedef long long LL;

const int MAXN = 5e06 + 10;
const int MAXM = 3000 + 10;

int prime[MAXN / 10];
int vis[MAXN]= {0};
int pcnt = 0;
int mu[MAXN]= {0};
LL phi[MAXN]= {0};
int sumu[MAXN]= {0};
LL sumphi[MAXN]= {0};
const int MAX = 4e06 + 5e05;
void linear_sieve () {
	mu[1] = phi[1] = 1;
	for (int i = 2; i <= MAX; i ++) {
		if (! vis[i]) {
			prime[++ pcnt] = i;
			mu[i] = - 1, phi[i] = i - 1;
		}
		for (int j = 1; j <= pcnt && i * prime[j] <= MAX; j ++) {
			vis[i * prime[j]] = 1;
			if (! (i % prime[j])) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			mu[i * prime[j]] = - mu[i];
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
	for (int i = 1; i <= MAX; i ++) {
		sumu[i] = sumu[i - 1] + mu[i];
		sumphi[i] = sumphi[i - 1] + phi[i];
	}
}

int T;

int N;
int mapmu[MAXM];
LL maphi[MAXM];
bool vmu[MAXM]= {false}, vphi[MAXM]= {false};

int mu_sieve (int n) {
	if (n <= MAX) return sumu[n];
	if (vmu[N / n]) return mapmu[N / n];
	int total = 1;
	for (int l = 2, r; l <= n; l = r + 1) {
		r = n / (n / l);
		total -= (r - l + 1) * mu_sieve (n / l);
	}
	vmu[N / n] = true;
	return mapmu[N / n] = total;
}
LL phi_sieve (int n) {
	if (n <= MAX) return sumphi[n];
	if (vphi[N / n]) return maphi[N / n];
	LL total = n * 1ll * (n + 1) / 2ll;
	for (int l = 2, r; l <= n; l = r + 1) {
		r = n / (n / l);
		total -= 1ll * (r - l + 1) * phi_sieve (n / l);
	}
	vphi[N / n] = true;
	return maphi[N / n] = total;
}

int main () {
	linear_sieve ();
	scanf ("%d", & T);
	for (int Case = 1; Case <= T; Case ++) {
		memset (vmu, false, sizeof (vmu));
		memset (vphi, false, sizeof (vphi));
		scanf ("%d", & N);
		LL ans1 = phi_sieve (N);
		int ans2 = mu_sieve (N);
		printf ("%lld %d\n", ans1, ans2);
	}

	return 0;
}