思路与算法

质因数分解x=∏pi^ei。严格整除链每步至少增加一个质因子，最长长度L=Σei；要达到最长，每步必须恰乘一个素数。不同链对应这个多重素数集合的排列，因此数量=L!/∏ei!。x1时L0，0!给唯一空链。

正确性说明

链的每项都整除x，最后一项若非x还可补x，故最长链末项为x。把每次相邻比和首项分解为素因子，质因子总数至多L，链长≤L。逐个乘入素因子达到L，且恰长L时每步比都必须是素数。相同素因子交换不产生新链，其余次序唯一决定前缀积链，故多重排列公式精确计数。

复杂度

试除分解O(sqrt x)，阶乘预处理O(log x)且本域最多20；每组O(sqrt x)，额外O(log x)，保存20阶乘为常数空间。

易错点

链必须严格递增，否则可重复因子无限长。首项大于1；x1只有空链。20!仍在有符号64位内，先完整算分母乘积再整除，不要逐步不整除截断。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<long long> fac(21, 1);
    for (int i = 1; i <= 20; i++)
        fac[i] = fac[i - 1] * i;
    int x;
    while (cin >> x) {
        int n = x, len = 0;
        long long den = 1;
        for (int p = 2; p * p <= n; p++)
            if (n % p == 0) {
                int a = 0;
                while (n % p == 0) {
                    n /= p;
                    a++;
                }
                len += a;
                den *= fac[a];
            }
        if (n > 1)
            len++;
        cout << len << ' ' << fac[len] / den << '\n';
    }
}