P11253 [GDKOI2023 普及组] 小学生数学题

1
#include <bits/stdc++.h>
2
#define MOD 998244353
3
#define N 20000010
4
using namespace std;
5

6
typedef long long ll;
7

8
int n, k;
9
int cnt = 0;
10
ll prime[N], p[N];
11
bool st[N];
12

13
ll qpow(ll a, ll b) {
14
    ll res = 1;
15
    while (b) {
16
        if (b & 1) res = res * a % MOD;
17
        a = a * a % MOD;
18
        b >>= 1;
19
    }
20
    return res % MOD;
21
}
22

23
ll inv(ll x) {
24
    return qpow(x, MOD - 2);
25
}
26

27
void sieve() {
28
    p[1] = 1;
29
    for (int i = 2; i <= n; i++) {
30
        if (!st[i]) {
31
            prime[++cnt] = i;
32
            p[i] = inv(qpow(i, k));
33
        }
34
        st[i] = true;
35
        for (int j = 1; i * prime[j] <= n; j++) {
36
            if (prime[j] > p[i] || j > cnt) break;
37
            st[i * prime[j]] = true;
38
            p[i * prime[j]] = p[prime[j]] * p[i] % MOD; // 维护积性函数
39
            if (i % prime[j] == 0) break;
40
        }
41
    }
42
}
43

44
int main() {
45
    ios::sync_with_stdio(false);
46
    cin.tie(nullptr);
47
    cout.tie(nullptr);
48

49
    cin >> n >> k;
50
    sieve();
51
    ll fac = 1;
52
    ll ans = 0;
53
    for (int i = 1; i <= n; i++) {
54
        fac = fac * i % MOD; // 线性维护阶乘
55
        ans = (ans + fac * p[i] % MOD) % MOD; // 计算
56
    }
57
    cout << ans << endl;
58
    return 0;
59
}