题解：CF757E Bash Plays with Functions

KarmaticEnding · 2025-12-31 18:40:55 · 题解

又是一道我不会的典题。

以下用 \omega(n) 表示 n 的不同质因数种类数。

第一个结论：f_0(n) = 2^{\omega(n)}。

::::info[证明]

对于任意正整数 n，设 \displaystyle n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots \times p_{\omega(n)}^{\alpha_{\omega(n)}} = \prod_{i = 1}^{\omega(n)} p_i^{\alpha_i}，也即 n 的质因数分解，其中 p_1, p_2, \dots, p_{\omega(n)} 是互不相同的质数，而 \alpha_1, \alpha_2, \dots, \alpha_{\omega(n)} 则是质数对应的次数。

根据题意，f_0(n) = \displaystyle\sum_{d \mid n}\left[\gcd\left(d, \dfrac{n}{d}\right) = 1\right]。要使 \gcd\left(d, \dfrac{n}{d}\right) = 1，当且仅当 d 和 \dfrac{n}{d} 没有公共质因数。这也等价于，对于 n 的每一个质因子 p_i，其要么是 d 的因数，要么是 \dfrac{n}{d} 的因数，不能同时是两者的因数。所以对于 n 的每个质因子 p_i 有两种选择，一共有 \omega(n) 个质因子，那么 f_0(n) = 2^{\omega(n)}。

::::

第二个结论：f_0 是积性函数。

::::info[证明]

对于任意两个互质的正整数 x 和 y，有

::::info[第二行到第三行推导的说明]

设 \displaystyle x = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots \times p_{\omega(x)}^{\alpha_{\omega(x)}}, y = p_{\omega(x) + 1}^{\alpha_{\omega(x) + 1}} \times p_{\omega(x) + 2}^{\alpha_{\omega(x) + 2}} \times \dots \times p_{\omega(x) + \omega(y)}^{\alpha_{\omega(x) + \omega(y)}}。因为 x 和 y 互质，所以 x 和 y 没有公共质因子，所以 p_1, p_2, \dots, p_{\omega(x)}, p_{\omega(x) + 1}, p_{\omega(x) + 2}, \dots, p_{\omega(x) + \omega(y)} 互不相同，所以 x\cdot y = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots \times p_{\omega(x)}^{\alpha_{\omega(x)}} \times p_{\omega(x) + 1}^{\alpha_{\omega(x) + 1}} \times p_{\omega(x) + 2}^{\alpha_{\omega(x) + 2}} \times \dots \times p_{\omega(x) + \omega(y)}^{\alpha_{\omega(x) + \omega(y)}}，那么 \omega(x \cdot y) = \omega(x) + \omega(y)。

::::

都看到这了，基本可以锁定本题跟积性函数脱不了关系了。读者可以自行想想接下来怎么做。

把题目中的公式转换一下：

第三个结论：对于任意的 r，有 f_r 是积性函数。

::::info[证明]

对于任意正整数 x 和 y，若有 \gcd(x, y) = 1，那么对于任意 x\cdot y 的因数 d，d 可以唯一写成 d = d_1 \cdot d_2，其中 d_1 \mid x, d_2 \mid y，且 \gcd(d_1, d_2) = 1。具体证明思路可以参照第一个结论的证明（把第一个结论的证明倒过来）。

那么考虑归纳法。如果我们已经证明了 f_{r - 1} 是积性函数：

所以 f_r 也是积性函数。

::::

都看到积性函数了，不难想到把 n 拆成 p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots \times p_{\omega(n)}^{\alpha_{\omega(n)}} 来处理（可以通过线性筛处理出每个数的最小质因子来拆）。接下来我们来想：f_r(p^k) 怎么求（其中 p 是质数）？

对于任意的 p 和 k，f_0(p^k) 的值都是 2（因为只有 (1, p_k) 和 (p_k, 1) 这两对是互质的），而 \displaystyle f_r(p^k) = \sum_{i = 0}^{k} f_{r - 1}(p^k)，不难发现 f_r(p^k) 的值跟 p 具体是什么是无关的，而 r 的值域是 [0, 10^6]，k 的值域是 [1, 19]，所以容易想到通过 O(r \cdot k) 递推的方式求 f_r(p^k)。

而 f_r(n) = f_r(p_1^{\alpha_1}) \times f_r(p_2^{\alpha_2}) \times \dots \times f_r(p_{\omega(n)}^{\alpha_{\omega(n)}})，所以 f_r(n) 可以在 O(\log n) 的时间内求出。

于是本题做完了。本题的难点在于注意到积性函数。

#include <cstdio>
const int mod = 1e9 + 7;
inline void read(int &x) // 快读
{
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    for (; c >= '0' && c <= '9'; c = getchar())
        x = (x << 3) + (x << 1) + (c & 15);
}
const int MAXN = 1e6 + 7;
inline int M(const int &x) { return x >= mod ? x - mod : x; } // 处理 [mod, 2mod) 之内的数
int T, n, m, ans, cp, p[MAXN], mp[MAXN], f[MAXN][21], pf[21];
inline void sieve() // 欧拉筛处理出每个数的最小质因子
{
    for (int i = 2; i < MAXN; ++i)
    {
        !mp[i] && (p[++cp] = mp[i] = i);
        for (int j = 1; i * p[j] < MAXN; ++j)
        {
            mp[i * p[j]] = p[j];
            if (mp[i] == p[j])
                break;
        }
    }
}
inline void prework()
{
    sieve(), pf[0] = 1; // f[r][k] 表示 f_r(p^k) 的值
    for (int i = 1; i < MAXN; ++i)
        f[i][0] = 1; // 对于任意的 r，f_r(1) 都是 1
    for (int i = 1; i < 21; ++i) // 对于任意的 k，f_0(p^k) 都是 2
        f[0][i] = 2, pf[i] = pf[i - 1] + 2; // pf 是前缀和优化
    for (int i = 1; i < MAXN; ++i)
        for (int j = 1; j < 21; ++j)
            f[i][j] = pf[j], pf[j] = M(pf[j - 1] + f[i][j]); // 递推，pf 数组可以复用
}
inline void solve()
{
    read(m), read(n), ans = 1;
    for (int c = 0, pr; n != 1; ans = (long long)(ans) * f[m][c] % mod, c = 0)
        for (pr = mp[n]; n % pr == 0; n /= pr) // 拆出来一个质因数
            ++c; // 计算质因数的次数，因为 f_r(p^k) 跟 p 是无关的，所以可以只计算 k
    printf("%d\n", ans);
}
int main()
{
    for (prework(), read(T); T; --T)
        solve();
    return 0;
}