Name

题目描述（精简版）

已知常数 (n) 和数论函数 (f_i(x))： [ f_0(x) = \begin{cases} 1 & x = n \ 0 & x \ne n \end{cases} ] [ f_i(x) = \sum_{x \mid d, x < d} f_{i-1}(d) ] 要求计算 (\sum_{i=0}^m f_i(1) \pmod p)。 数据范围：(n \le 10^{18})，(m \le 10^9)，(p \le 10^9)，保证 (n) 不含超过 (10^6) 的质因子。

---

题解：从多重求和到插板法+容斥

1. 题意转化

$$f_0(x)=[x==n]$$$$f_1(x)=[x==1]$$

[ f_i(1) = \sum_{a_i|n, a_i>1} \sum_{a_{i-1}|\frac{n}{a_i}, a_{i-1}>1} \dots \sum_{a_1|\frac{n}{\prod_{j=2}^i a_j}} [a_1=1] ] 根据你的推导，(f_i(1)) 的物理意义就是：长度为 (i) 的严格递增的 (n) 的因数数列的数量，即： [ 1 = d_0 < d_1 < d_2 < \dots < d_i = n ] 其中 (d_{j-1} \mid d_j)。

2. 降维打击：映射到质因数指数

直接算因数链复杂度极高（图论中求路径数是指数级的），我们需要映射到质因数指数。 设 (n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k})。 每个因数 (d_j) 对应一个指数向量 ((e_{j,1}, e_{j,2}, \dots, e_{j,k}))。 (d_{j-1} \mid d_j) 且 (d_{j-1} < d_j)，等价于：对于这 (i) 步，每一步至少有一个质因数的指数增加，且最终从全 (0) 变到了 (a_1, a_2, \dots, a_k)。

3. 容斥原理（二项式反演）

放宽条件：如果我们允许因数相等（即允许某一步所有质因数指数都不变），问题就变成了非常经典的插板法。 对于第 (j) 个质因数，要把指数 (a_j) 分配给 (i) 步，允许某步分配 (0)，方案数为 (\binom{a_j + i - 1}{i - 1})。 由于各质因数独立，总的“允许相等”的方案数：

$$P(i)=\prod _{j=1}^k(\genfrac{}{}{0ex}{}{a_j+i-1}{i-1})$$

根据二项式反演，恰好 (i) 步（严格递增）的方案数 (f_i(1)) 为： [ f_i(1) = \sum_{k=0}^i (-1)^{i-k} \binom{i}{k} P(k) ] (注意：(n>1) 时 (P(0)=0))

4. 复杂度玄机：(m) 是纸老虎

(m) 高达 (10^9)，但 (n \le 10^{18})，即使 (n) 全由 (2) 组成，质因数指数的总和 (A = \sum a_j \le \log_2(10^{18}) \approx 60)。 因为 (f_i(1)) 代表严格递增的因数链，链长（步数）最多也就是 (A)。 因此 当 (i > A) 时，(f_i(1) = 0)。 我们只需要令 (m = \min(m, A))，复杂度骤降至 (O(A^2)) 级别。

5. 代码细节

• 分解质因数：(n) 不含超过 (10^6) 的质因子，直接试除到 (10^6) 即可。
• 组合数取模：(p) 不一定是质数，不能求逆元。但 (A \le 60)，(P(k)) 里的组合数上界也就 (120) 左右，直接利用 __int128 计算阶乘/连乘来防溢出即可。

---

C++ 完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
ll n, m, p;
vector<int> a; // 存储质因数的指数

// 计算组合数 C(N, K) % p
// 这里 N <= 120 左右，K <= 60，直接暴力乘除，用 __int128 防溢出
ll binom(ll N, ll K, ll p) {
    if (K < 0 || K > N) return 0;
    __int128 res = 1;
    for (ll i = 1; i <= K; ++i) {
        res = res * (N - K + i) / i;
    }
    return (ll)(res % p);
}

// 计算 P(x)，即允许有原地踏步的方案数
ll calc_P(ll x) {
    if (x == 0) return 0; // 如果 n>1，0步肯定到不了
    ll res = 1;
    for (int a_j : a) {
        // 插板法: C(a_j + x - 1, x - 1)
        ll c = binom(a_j + x - 1, x - 1, p);
        res = (res * c) % p;
    }
    return res;
}

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> p;

    // 1. 质因数分解求指数
    ll temp = n;
    for (ll i = 2; i * i <= temp && i <= 1000000; ++i) {
        if (temp % i == 0) {
            int cnt = 0;
            while (temp % i == 0) {
                temp /= i;
                cnt++;
            }
            a.push_back(cnt);
        }
    }
    if (temp > 1) a.push_back(1);

    // 2. 计算质因数指数总和 A
    int A = 0;
    for (int cnt : a) A += cnt;

    // 3. m 极大，但链长不可能超过 A
    m = min(m, (ll)A);

    vector<ll> f(m + 1, 0);
    ll ans = 0;

    // 4. 二项式反演求 f_i(1)
    for (int i = 0; i <= m; ++i) {
        ll sum = 0;
        for (int k = 0; k <= i; ++k) {
            ll c = binom(i, k, p);
            ll Pk = calc_P(k);
            ll term = (c * Pk) % p;

            // 容斥原理: (-1)^(i-k)
            if ((i - k) % 2 == 1) {
                term = (p - term) % p;
            }
            sum = (sum + term) % p;
        }
        f[i] = sum;
        ans = (ans + f[i]) % p; // 累加所有 f_i(1)
    }

    // 注意：如果输入 n=1，A=0, m=0，f_0(1) 逻辑上为 1
    // 但因为 n 是正整数，题设一般 n>=2 或根据数据范围特殊处理
    if (n == 1) {
        cout << (1 % p) << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

复杂度分析

• 时间复杂度：质因数分解 (\mathcal{O}(\sqrt{n}))（最高 (10^6)）；计算组合数与二项式反演 (\mathcal{O}(A^2 \log A))（(A \le 60)，极快）。整体复杂度 (\mathcal{O}(10^6 + A^2 \log A))，完全可以通过。
• 空间复杂度：(\mathcal{O}(A))，用于存储质因数指数和数组 f。