题目描述
https://loj.ac/p/6682
简要题意：给定 $n$，求 $\frac{1}{2}\sum_{i=1}^n\sigma_0^2(i)-\sigma_0(i)$
$n\le 10^{10}$
Solution
注意到 $\sum_{i=1}^n\sigma_0(i)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$，对于 $\sum_{i=1}^n\sigma_0^2(i)$ 我们可以考虑用 $Min\underline{}25$ 筛
我们令 $f(x)=\sigma_0(x)^2$，这个东西显然是积性函数，且 $f(p^x)=(x+1)^2$
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
| #include <iostream>
#include <cmath>
#define ll long long
#define maxn 200010
using namespace std;
const int p = 998244353;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
ll n;
int pri[maxn], cnt; bool isp[maxn]; ll sp[maxn];
void init_isp(int n) {
for (int i = 2; i <= n; ++i) {
if (!isp[i]) {
pri[++cnt] = i;
sp[cnt] = sp[cnt - 1] + 4;
}
for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
ll id1[maxn], id2[maxn], Sn;
int get_id(ll x) { return x <= Sn ? id1[x] : id2[n / x]; }
ll g[maxn], w[maxn]; int num;
void init_min25(ll n) {
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l); w[++num] = n / l;
g[num] = 4 * (n / l) % p - 4;
if (w[num] <= Sn) id1[w[num]] = num;
else id2[n / w[num]] = num;
}
for (int i = 1; i <= cnt; ++i)
for (int j = 1; j <= num && 1ll * pri[i] * pri[i] <= w[j]; ++j)
g[j] = (g[j] - (g[get_id(w[j] / pri[i])] - sp[i - 1])) % p;
}
ll S(ll n, int m) {
if (pri[m] >= n) return 0;
ll ans = (g[get_id(n)] - sp[m]) % p;
for (int i = m + 1; i <= cnt && 1ll * pri[i] * pri[i] <= n; ++i)
for (ll x = 1, mul = pri[i]; mul <= n; mul *= pri[i], ++x)
ans = (ans + (x + 1) * (x + 1) * (S(n / mul, i) + (x > 1))) % p;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n; Sn = sqrt(n); init_isp(Sn); init_min25(n);
ll ans = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans = (ans - (r - l + 1) % p * (n / l)) % p;
} ans = (ans + S(n, 0) + 1) * pow_mod(2, p - 2) % p;
cout << (ans + p) % p << "\n";
return 0;
}
|