题解：P9920 「RiOI-03」变换，反演

dingziyang888 · 2026-04-22 22:06:37 · 题解

一些闲话

五年级蒟蒻的第一篇黑题题解，求过，求赞。

~~顺着做题计划做题，顺便补一下这周掉的一点点社贡分。~~

这个题跟我从早上 8 点纠缠到晚上 10 点，题挺好，~~就是这个 Subtask 分治有点恶心~~。

本文章同步发表于博客园。

题意

给定一个积性函数 f(x)，但不保证 f(1)=1，给定莫比乌斯变换

g(x)=\sum_{d \mid x} f(d)

中的 k 组值，接下来 t 组询问，每组询问给定一个 n，求 f(n) \bmod 998244353。

前置芝士

常见狄利克雷卷积；
莫比乌斯函数 \mu(n)；
Miller-Rabin 素性测试；
Pollard-Rho 大数分解。

下面将逐一分析每一个 Subtask 的解法。

本文中的质因数分解（试除法、Miller-Rabin 素性测试、Pollard-Rho 大数分解）为简洁，均用一个函数实现，相关函数如下：

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

bool Miller_Rabin(std::int64_t n){
    if (n < 2 || !(n & 1)) return false;
    if (n == 2 || n == 3) return true;
    std::int64_t d = n - 1, s = 0;
    while (!(d & 1)) d >>= 1, ++s;
    static std::int64_t bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for (std::int64_t a : bases)
        if (a % n){
            std::int64_t x = binpow(a, d, n); bool flag = false;
            if (x == 1 || x == n - 1) continue;
            for (std::int64_t r = 1; r < s; r++){
                x = (__int128)x * x % n;
                if (x == n - 1){ flag = true; break; }
            }
            if (!flag) return false;
        }
    return true;
}

std::int64_t Pollard_rho(std::int64_t n){
    if (!(n & 1)) return 2;
    if (!(n % 3)) return 3;
    while (true){
        std::int64_t c = std::uniform_int_distribution <std::int64_t> (1, n - 1) (rng);
        auto f = [&] (std::int64_t x){ return ((__int128)x * x % n + c) % n; };
        std::int64_t x = std::uniform_int_distribution <std::int64_t> (2, n - 2) (rng);
        std::int64_t y = x, d = 1;
        while (d == 1) x = f(x), y = f(f(y)), d = std::gcd(std::abs(x - y), n);
        if (d != n) return d;
    }
}

void fac_rec(std::int64_t n, std::map <std::int64_t, std::int64_t>& res){
    if (n == 1) return;
    if (Miller_Rabin(n)) return void(res[n]++);
    std::int64_t d = Pollard_rho(n);
    fac_rec(d, res), fac_rec(n / d, res);
}

std::map <std::int64_t, std::int64_t> fac(std::int64_t n){ // 均放在该函数中实现
    std::map <std::int64_t, std::int64_t> res;
    for (std::int64_t p = 2; p <= 1e6 && p * p <= n; p++)
        if (n % p == 0){
            std::int64_t exps = 0;
            while (n % p == 0) n /= p, ++exps;
            res[p] = exps;
        }
    if (n > 1){
        if (Miller_Rabin(n)) res[n] = 1;
        else fac_rec(n, res);
    }
    return res;
}

\text{Epsilon}

数据范围：n \le 10^6,\ k=100,\ t=10。

我们发现 g(n)=\varepsilon(n)，于是 f=g*\mu=\varepsilon*\mu=\mu，又因为 n \le 10^6，线性筛预处理即可，时间复杂度 O(n)。

void sieve(std::int64_t n){
    mu[1] = 1;
    for (std::int64_t i = 2; i <= n; i++){
        if (!vis[i]) prime[++tot] = i, mu[i] = -1;
        for (std::int64_t j = 1; j <= tot && i * prime[j] <= n; j++){
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0){
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
}

void Epsilon(){
    sieve(maxn - 5);
    for (std::int64_t i = 1; i <= t; i++)
        if (query[i] == 1) std::cout << 1 << std::endl;
        else std::cout << (mu[query[i]] + mod) % mod << std::endl;
}

\text{Division}

数据范围：n \le 10^9,\ k=100,\ t=10。

注意到 g(n)=d(n)，从而 f(n)=1，于是所有询问均输出 1 即可。

void Division(){
    for (std::int64_t i = 1; i <= t; i++)
        std::cout << 1 << std::endl;
}

\text{Unknown}

数据范围：n \le 10^{18},\ k=1,\ t=10。

这个 n 弄这么大是何意味呢？我们发现仅给出了 g(1)=0，从而 f(1)=0，由积性得 f(n)=0，于是所有询问均输出 0 即可。

void Unknown(){
    for (std::int64_t i = 1; i <= t; i++)
        std::cout << 0 << std::endl;
}

\text{Random}

数据范围：n \le 10^5,\ k=10^5,\ t=10^5。

我们观察数据范围发现 n \le k，即所有询问的 n 均已给出，反演：

f(n)=g(n)-\sum_{d \mid n,\ d<n} f(d)。

从小到大递推计算 f(i)\ (1\le i\le k) 即可，时间复杂度 O(k \log k)。

void Random(){
    for (std::int64_t i = 1; i <= k; i++)
        g[giv[i].first] = giv[i].second % mod;
    f[1] = g[1];
    for (std::int64_t i = 2; i <= k; i++){
        f[i] = g[i];
        for (std::int64_t j = 1; j * j <= i; j++)
            if (i % j == 0){
                if (j != i) f[i] = (f[i] - f[j]) % mod;
                if ((i / j) != i && (i / j) != j) f[i] = (f[i] - f[i / j]) % mod;
            }
    }
    for (std::int64_t i = 1; i <= t; i++)
        if (query[i] <= k) std::cout << (f[query[i]] + mod) % mod << std::endl;
        else std::cout << 0 << std::endl;
}

\text{Double}

数据范围：n \le 10^9,\ k=100,\ t=10。

对于已知的 g 做一次莫比乌斯反演 h=g*\mu，发现并没有什么用，再反演一次得到 p=h*\mu，结果均为完全平方数，开方后得到 \varphi(n)^2，从而 f=\varphi*1，即

f(n)=\sum_{d \mid n} \varphi(d)^2。

由于 n \le 10^9，我们直接对于询问做质因子分解，利用积性有

f(p^e)=\sum_{i=0}^e \varphi(p^i)^2=1+\sum_{i=1}^e \bigl(p^{i-1}(p-1)\bigr)^2，

然后

f(n)=\prod f(p^e)。

试除法试到 10^6，剩余部分 Miller-Rabin 素性测试即可，可以做到 O(\sqrt n)。

void Double(){
    auto pows = [&](std::int64_t p, std::int64_t e) -> std::int64_t{
        std::int64_t res = 1, phi = 1, pk = 1;
        for (std::int64_t i = 1; i <= e; i++){
            pk = pk * p % mod;
            if (i == 1) phi = (p - 1) % mod;
            else phi = phi * p % mod;
            res = (res + phi * phi) % mod;
        }
        return res;
    };
    for (std::int64_t i = 1; i <= t; i++){
        std::int64_t ans = 1;
        for (auto [p, e] : fac(query[i])) ans = ans * pows(p % mod, e) % mod;
        std::cout << ans << std::endl;
    }
}

\text{Hack}

数据范围：n \le 10^9,\ k=31623,\ t=1。

观察反演后的结果，有 f(p^k)=p^{2k-1}，对于 n=pq（其中 p,q 为质数），有 f(n)=n。

我们对于询问分解质因数，如果仅有两个质因子且指数均为 1，直接输出 n \bmod 998244353，否则计算 \prod p^{2e-1} \bmod 998244353。由于 n \le 10^9，试除加上 Miller-Rabin 素性测试即可，可以做到 O(\sqrt n)。

void Hack(){
    for (std::int64_t i = 1; i <= t; i++){
        auto fs = fac(query[i]);
        if (fs.size() == 2 && fs.begin()->second == 1 && std::next(fs.begin())->second == 1)
            std::cout << query[i] % mod << std::endl;
        else {
            std::int64_t ans = 1;
            for (auto [p, e] : fs) ans = ans * binpow(p % mod, 2 * e - 1, mod) % mod;
            std::cout << ans << std::endl;
        }
    }
}

\text{Square}

数据范围：n \le 10^{18},\ k=100,\ t=5。

我们发现 g(n)=n^2，反演 f=g*\mu，即

f(n)=\sum_{d \mid n} d^2\mu\!\left(\frac{n}{d}\right)。

根据积性，有

f(p^k)=p^{2k}-p^{2k-2}，

于是

f(n)=n^2 \prod_{p \mid n} (1-p^{-2})。

对于每个询问用 Pollard-Rho 分解质因数，计算上式，注意求逆元，这样速度快得飞起，为 O(n^{1/4})。

void Square(){
    for (std::int64_t i = 1; i <= t; i++){
        auto fs = fac(query[i]);
        auto ans = (query[i] % mod) * (query[i] % mod) % mod;
        for (auto [p, e] : fs){
            std::int64_t inv = binpow(p % mod, mod - 2, mod);
            inv = inv * inv % mod;
            ans = ans * ((1 - inv + mod) % mod) % mod;
        }
        std::cout << ans << std::endl;
    }
}

\text{Poly}

数据范围：n \le 10^9,\ k=10^5,\ t=100。

注意到 f(p^k) 为关于 p^k 的三次多项式，即

f(p^k)=114p^{3k}+514p^{2k}+1919p^k+810。

（上述多项式系数由拉格朗日插值得出，参见学习笔记。）

对询问的 n 分解质因数，对每个 p^e 代入多项式求值，乘起来即可，可以做到 O(\sqrt n)。

\text{Thanks}

数据范围：n \le 10^5,\ k=4,\ t=10^5。

给了四个已知的 g 值，我们手算有 f(1)=f(2)=f(4)=1,\ f(3)=0,\ f(5) 无法确定，我们猜测 f(n)=n^2 \bmod 3，符合积性。

void Thanks(){
    for (std::int64_t i = 1; i <= t; i++)
        std::cout << ((query[i] % 3) * (query[i] % 3) % 3) << std::endl;
}

无注释纯享版代码。