Loj 6682 梦中的数论

Posted on | Views:

min_25 筛.

先枚举 $i$ ,答案就变成了
$$
ans=\sum_{i=1}^n \binom{\sigma_0(i)}{2}\\
=\frac {\sum_{i=1}^n \sigma_0^2(i)-\sum_{i=1}^n \sigma_0(i)} 2 \\
=\frac {\sum_{i=1}^n \sigma_0^2(i)-\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor} 2
$$
后面那个 $\sum$ 可以直接整除分块 $O(\sqrt n)$ 求出.

对于前面那个 $\sum$ ,注意到 $\sigma_0^2(x)$ 也是积性函数,且当 $p$ 为质数时, $\sigma_0^2(p^k)=(k+1)^2$ ,容易计算.

于是可以考虑用 min_25 筛求出其前缀和,时间复杂度 $O(\frac{n^{\frac 3 4}}{\log n})$ .

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//%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 P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 2e5 + 10;
ll n, w[N];
int sqr, prime[N], ism[N], cnt = 0, g[N], id1[N], id2[N], tot = 0, ans = 0;
int id(ll x)
{
	if (x <= sqr)
		return id1[x];
	return id2[n / x];
}
void init()
{
	ism[1] = 1;
	for (int i = 2; i <= sqr; ++i)
	{
		if (!ism[i])
			prime[++cnt] = i;
		for (int j = 1; j <= cnt && prime[j] <= sqr / i; ++j)
		{
			ism[i * prime[j]] = 1;
			if (i % prime[j] == 0)
				break;
		}
	}
	for (ll l = 1, r; l <= n; l = r + 1) 
	{
		r = n / (n / l);
		inc(ans, P - mul(n / l % P, (r - l + 1) % P));
		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) % P;
	for (int j = 1; j <= cnt; ++j)
		for (int i = 1; i <= tot && prime[j] <= w[i] / prime[j]; ++i)
		{
			int k = id(w[i] / prime[j]);
			inc(g[i], P - add(g[k], add(1, P - j)));
		}
	for (int i = 1; i <= tot; ++i)
		g[i] = mul(g[i], 4);
}
int S(ll x, int j)
{
	if (x <= 1 || prime[j] > x)
		return 0;
	int s = add(g[id(x)], P - mul(4, j - 1));
	for (int k = j; k <= cnt && prime[k] <= x / prime[k]; ++k)
	{
		ll pw = prime[k], t = 1LL * prime[k] * prime[k];
		for (int e = 1; t <= x; ++e)
		{
			inc(s, mul((e + 1) * (e + 1), S(x / pw, k + 1)));
			inc(s, (e + 2) * (e + 2));
			pw *= prime[k], t *= prime[k];
		}
	}
	return s;
}
int main()
{
	n = read(), sqr = ceil(sqrt(n));
	init();
	inc(ans, 1);
	inc(ans, S(n, 1));
	ans = mul(ans, (P + 1) >> 1);
	printf("%d\n", ans);
	return 0;
}