题解 | F. 除数链

F. 除数链

和因子有关，直接质因数分解

我们定义 表示 ，则 表示

题目要求找到最长的除数链，我们发现对于 ， 代表的 和 代表的 满足 且

说人话：除数链往右扫的过程中，这个 元组中，至少有一个元素增加恰好

要最长，肯定是从 变到

我们需要加 次，定义 表示加到第 个位置

问题变成给你一个 的字符串，有多少种排列方案

显然根据高中数学常识，这就是

预处理 阶乘 和 阶乘逆元 即可

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

constexpr ll MOD = 1000000007;
constexpr ll XX = __lg(1000000000000) + 2;
ll jc[XX + 1];
void init()
{
    jc[0] = jc[1] = 1;
    foreach (i, 2, XX)
        jc[i] = jc[i - 1] * i % MOD;
}

template <ll MOD>
ll qpow(ll x, ll p)
{
    ll r = 1;
    for (; p; p >>= 1, x = x * x % MOD)
        if (p & 1) r = r * x % MOD;
    return r;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    init();

    ll n;
    cin >> n;

    vector<ll> ct;
    ct.reserve(85714);

    for (ll i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            int cnt = 0;
            while (n % i == 0)
                n /= i, ++cnt;
            ct.emplace_back(cnt);
        }
    }
    if (n > 1) ct.emplace_back(1);

    ll len = accumulate(ct.begin(), ct.end(), 0ll) + 1;
    ll u = jc[len - 1], v = 1;
    for (auto c : ct)
        v = v * jc[c] % MOD;
    cout << len << " " << u * qpow<MOD>(v, MOD - 2) % MOD << "\n";

    return 0;
}

扩展思考：如果 ，还能做吗？