Loj 6181 某个套路求和题

Posted on | Views:

复习了一下 min_25 筛.

考虑化简 $f(n)=\prod_{d|n} \mu(d)$ .

当 $n$ 有平方因子时, $f(n) = 0$ ,否则我们考虑有几个 $\mu(d)=-1$ ,就可以算出 $\mu(n)$ .

记 $n$ 有 $\omega(n)$ 种不同的质因子,由于 $n$ 没有平方因子,所以各个质因子的次数都是 $1$ .

$d$ 是 $n$ 的约数可以看做从 $\omega(n)$ 个质因子中选出一些乘起来组成的,而 $\mu(d)=-1$ 等价于选了奇数个.

那么显然有 $2^{\omega(n)-1}$ 种选法,只有当 $n$ 为质数时有奇数个 $\mu(d)=-1$ ,其他情况都有偶数个.

于是可以得出
$$
ans=\sum_{i=1}^n\mu^2(i) -\sum_{i=1}^n 2\times [i\in Prime]
$$
后者是 $1$ 到 $n$ 中质数个数的 $2$ 倍,可以用 min_25 筛求出.

考虑如何求 $\sum \mu^2(i)$ ,记 $p(n)=\max_{d^2|n} \lbrace d\rbrace$ 表示 $n$ 的最大平方因子,则
$$
\sum_{i=1}^n \mu^2(i) \\
=\sum_{i=1}^n [p(i)=1] \\
=\sum_{d=1}^n \mu(d) \sum_{d|p(i)}1 \\
=\sum_{d=1}^n\mu(d) \sum_{d^2|i} 1\\
=\sum_{d=1}^n \mu(d) \lfloor \frac n {d^2} \rfloor
$$
于是筛出 $\sqrt n$ 以内的 $\mu$ ,就可以在 $O(\sqrt n)$ 内计算出 $\sum \mu^2(i)$ 了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int N = 1e5 + 10, P = 998244353;
ll w[N * 2], g[N * 2], n;
int sqr, mu[N], prime[N], cnt = 0, ism[N], id1[N], id2[N], tot = 0;
void init()
{
	ism[1] = 1, mu[1] = 1;
	for (int i = 2; i <= sqr; ++i)
	{
		if (!ism[i])
			prime[++cnt] = i, mu[i] = -1;
		for (int j = 1; i * prime[j] <= sqr && j <= cnt; ++j)
		{
			ism[i * prime[j]] = 1;
			if (i % prime[j] == 0)
				break;
			mu[i * prime[j]] = -mu[i]; 
		}
	}
	for (ll l = 1, r; l <= n; l = r + 1)
	{
		r = n / (n / l);
		w[++tot] = n / l;
		if (n / l <= sqr)
			id1[n / l] = tot;
		else
			id2[n / (n / l)] = tot;
	}
	for (int i = 1; i <= tot; ++i)
		g[i] = w[i] - 1;
	for (int j = 1; j <= cnt; ++j)
		for (int i = 1; i <= tot && prime[j] <= w[i] / prime[j]; ++i)
		{
			ll k = w[i] / prime[j];
			if (k <= sqr)
				k = id1[k];
			else
				k = id2[n / k];
			g[i] -= g[k] - j + 1;
		}
}
int main()
{
	n = read(), sqr = ceil(sqrt(n));
	init();
	ll ans = 0;
	for (int i = 1; i <= n / i; ++i)
		ans += 1LL * mu[i] * (n / i / i);
	ans -= 2 * g[1];
	printf("%lld\n", (ans % P + P) % P);
	return 0;
}