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

您已获得最佳的阅读体验！

题目地址：P11253

题目难度：普及/提高+

题目来源：广东 2023

求出和式的值，

开始我以为这只是一道快速幂的大水题，敲了一个快速幂然后测试了一下大样例，发现 T 飞了。于是我又用上了不知从哪道题里学来的十进制快速幂，结果还是不行。最后我又类比十进制快速幂写了个百进制快速幂，希望能过一些点，最后还是全 T……

注意到维护阶乘的复杂度是，实际上该题的瓶颈在于如何快速求出内每个数的次幂。其次，注意到，也即，显然是一个积性函数。

又发现线性筛在筛去合数时有一个乘积的形式，于是我们可以借用这个思路，在筛去合数的同时维护这个函数。

#include <bits/stdc++.h>
#define MOD 998244353
#define N 20000010
using namespace std;

typedef long long ll;

int n, k;
int cnt = 0;
ll prime[N], p[N];
bool st[N];

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res % MOD;
}

ll inv(ll x) {
    return qpow(x, MOD - 2);
}

void sieve() {
    p[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            prime[++cnt] = i;
            p[i] = inv(qpow(i, k));
        }
        st[i] = true;
        for (int j = 1; i * prime[j] <= n; j++) {
            if (prime[j] > p[i] || j > cnt) break;
            st[i * prime[j]] = true;
            p[i * prime[j]] = p[prime[j]] * p[i] % MOD; // 维护积性函数
            if (i % prime[j] == 0) break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;
    sieve();
    ll fac = 1;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        fac = fac * i % MOD; // 线性维护阶乘
        ans = (ans + fac * p[i] % MOD) % MOD; // 计算
    }
    cout << ans << endl;
    return 0;
}