LOJ 6181 某个套路求和题

发表于 更新于 分类于

题目链接

和社论不一样的方法
## 题目
已知\(f(n) = \prod\limits_{d|n} \mu(d)\) 求\(\sum\limits_{i=1}^n f(i) \bmod 998244353\)，\(n\leq 10^{10}\)

分析

求\(\sum\limits_{i=1}^n\prod\limits_{d|i} \mu(d)\)
我们来观察一下\(\prod\limits_{d|i} \mu(d)\)有什么特点。

首先如果\(i\)有平方因子，那么它等于\(0\)
\(i\)为素数，等于\(1\)

其他情况，我们考虑有多少个约数\(\mu (d)=-1\)
我们把\(i\)唯一分解一下，一定等于\(\prod p-i^1\)
假设一共有\(cnt\)个素约数，那么\(d\)无非就是从些质约数里面选一些出来。
等于\(\binom{cnt}{1}+\binom{cnt}{3}+...+\binom{cnt}{2k+1}\)
也就是\(\sum_{i=1}^{cnt}\binom{cnt}{i}[i\nmid 2]=2^{cnt-1}\)
所以只有\(cnt=1\)时才为\(-1\)，\(cnt>1\)时都等于\(1\)，而\(cnt=1\)的情况已经讨论过了。

我们把素数和其他数分类讨论
\(ans=\sum_{i=1,i\not\in prime}^n\mu(i)^2-\sum_{i=1,i\in prime}^n{1}\) \(ans=\sum_{i=1}^n\mu(i)^2-\sum_{i=1}^n{2}\)

前面是积性函数前缀和，后面是素数个数。
这东西直接min25筛不就完了 为什么题解些这么麻烦啊 ?
最开始代码有点小问题，还以为不能这么做 同学帮我开了long long 竟然过了？

不过社论有\(O{\sqrt{n}}\)筛\(\sum\mu(i)^2\)的做法。 诶诶题解直接看这里好了link

代码

社论做法 

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 5, MOD = 998244353;
ll n, sum[N], g[N], w[N], sqr, mu[N];
int cnt, m, id1[N], id2[N], p[N];
bool vis[N];

void init(int m) {
    mu[1] = 1;
	for (int i = 2; i <= m; i++) {
		if (!vis[i]) p[++cnt] = i, mu[i] = -1;
		for (int j = 1; j <= cnt && i * p[j] <= m; j++) {
			vis[i * p[j]] = 1;
			if (i % p[j] == 0) break;
			mu[i * p[j]] = -mu[i];
		}
	}
}

int main() {
    scanf("%lld", &n);
	sqr = sqrt(n);
	init(sqr + 1);
	for (ll l = 1, r; l <= n; l = r + 1) {
		w[++m] = n / l;
		r = n / w[m];
		g[m] = (w[m] - 1ll + MOD) % MOD;
		if (w[m] <= sqr) id1[w[m]] = m;
		else id2[r] = m;
	}
	for (int j = 1; j <= cnt; j++)
		for (int i = 1; i <= m && p[j] * 1ll * p[j] <= w[i]; i++) {
			int k = (w[i] / p[j] <= sqr) ? id1[w[i] / p[j]] : id2[n / (w[i] / p[j])];
			g[i] = (g[i] -  (g[k] - j + 1) + MOD) % MOD;
		}
	ll res = 0;
	for (int i = 1; i <= n / i; i++)
		res = (res + mu[i] * 1ll * (n / i / i) % MOD) % MOD;
	res -= g[1] * 2;
	printf("%lld\n", (res % MOD + MOD) % MOD);
	return 0;
}

直接筛 

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 5, MOD = 998244353;
ll n, sum[N], g[N], w[N], sqr;
ll cnt, m, id1[N], id2[N], p[N];
bool vis[N];

void init(int m) {
    for (int i = 2; i <= m; i++) {
		if (!vis[i]) p[++cnt] = i;
		for (int j = 1; j <= cnt && i * p[j] <= m; j++) {
			vis[i * p[j]] = 1;
			if (i % p[j] == 0) break;
		}
	}
}

ll S(ll x, int y) {
	if (x <= 1 || p[y] > x) return 0;
	int k = (x <= sqr) ? id1[x] : id2[n / x];
	ll res = g[k] - (y - 1);
	for (int i = y; i <= cnt && p[i] * p[i] <= x; i++)
		res = (res + S(x / p[i], i + 1)) % MOD;
	return res;
}

int main() {
    scanf("%lld", &n);
	sqr = sqrt(n);
	init(sqr);
	for (ll l = 1, r; l <= n; l = r + 1) {
		w[++m] = n / l;
		r = n / w[m];
		g[m] = (w[m] - 1ll + MOD) % MOD;
		if (w[m] <= sqr) id1[w[m]] = m;
		else id2[r] = m;
	}
	for (int j = 1; j <= cnt; j++)
		for (int i = 1; i <= m && p[j] * 1ll * p[j] <= w[i]; i++) {
			int k = (w[i] / p[j] <= sqr) ? id1[w[i] / p[j]] : id2[n / (w[i] / p[j])];
			g[i] = (g[i] -  (g[k] - j + 1) + MOD) % MOD;
		}
	printf("%lld\n", ((-g[1] * 2 % MOD + MOD) % MOD + S(n, 1) + 1) % MOD);
	return 0;
}