题解：P7360 「JZOI-1」红包

· · 题解

前言：

好题啊，可惜各位大佬的莫反，容斥，一堆的式子我都看不懂啊，只看懂了 Corzica 大佬的做法，这里主要是对其做法的补充解释。

思路：

首先考虑对于每个质数 p，它对答案的贡献：若 \operatorname{lcm} 中含有 p^q，总共有 n^k 种方案，其中 \operatorname{lcm} 不含 p^q 的方案数是 n^k-(\frac{n}{p^q})^k，相减就是含 \operatorname{lcm} 的方案。对答案的贡献是 p^{n^k-(\frac{n}{p^q})^k}，为啥底数不是 p^q 呢，因为我们已经统计过了 \operatorname{lcm} 含有 p^{q-1},p^{q-2}...p 了，p^q 只多了 p 的贡献，所以底数是 p。

又因为读入的 k 很大，根据扩展欧拉定理和费马小定理，对于指数上的 n^k，k 模 φ(mod-1) 即可，指数的答案再模 mod-1。这样单次时间是 O(n\log{n}) 的，对于 \frac{n}{p^q}，发现可以整除分块，单次时间复杂度降至 O(\sqrt{n}\log{n})，可以通过。还有别的问题就看代码吧，实现也是比较简单的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int mod = 998244353;
const int phi = 402653184;//998244352 的phi值
int n, m, pr[N], cnt, f[N], T;
bool vis[N];
//快速幂
inline int quickpow(int x, int y, int mod) {
    if (y == 1)return x;
    if (y == 0)return 1;
    int g = quickpow(x, y / 2, mod);
    if (y & 1)return g * g % mod * x % mod;
    return g * g % mod;
}
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //f[i]记录i这个数是不是一个质数的 n 次方，是的话，是哪个质数，可以线性筛预处理
    n = 1e6;
    for (int i = 2; i <= n; i ++) {
        if (!vis[i]) {
            pr[++ cnt] = i;
            f[i] = i;
        }
        for (int j = 1; j <= cnt && i * pr[j] <= n; j ++) {
            vis[pr[j] * i] = 1;
            if (i % pr[j] == 0) {
                f[i * pr[j]] = f[i];
                break;
            }
        }
    }
    f[0] = 1;
    for (int i = 1; i <= n; i ++) {
        if (!f[i])f[i] = 1;
        f[i] = f[i - 1] * f[i] % mod;
    }
    //预处理前缀积
    cin >> T;
    while (T --) {
        cin >> n;
        string s;
        cin >> s;
        m = 0;
        for (int i = 0; i < s.size(); i ++) {
            m = m * 10 + s[i] - '0';
            if (m >= phi) m = m % phi + phi;
        }//读入时将k 模 φ(mod - 1),因为 k 在最后的式子上在指数的指数上
        int all = quickpow(n, m, mod - 1), ans = 1;
        //总是用 n ^ k 去减，可以直接算好
        for (int l = 1; l <= n; l ++) {
            int r = n / (n / l);//整除分块
            if (f[r] != f[l - 1]) {
                //f[r] / f[l - 1] 求 l ~ r 的积
                ans *= quickpow(f[r] * quickpow(f[l - 1], mod - 2, mod) % mod, (all - quickpow(n - n / l, m, mod - 1)/*减去 lcm 中没有 p ^ q 的方案*/ + mod - 1) % (mod - 1), mod);
                ans %= mod;
            }
            l = r;
        }
        cout << ans << '\n';
    }
    return 0;
}