P4912 因式分解（提高）

解题思路

第一步，理解题意。 把自然数N拆成若干个大于1的自然数相乘，顺序不同算不同的方案，单独一个N也算一种方案（N=N）。例如N=12共有8种方案：12、6×2、4×3、3×4、3×2×2、2×6、2×3×2、2×2×3。我们要统计方案总数。

第二步，把问题转化成递推。 设f(x)表示把x分解成大于1的因子乘积的方案总数。观察发现：如果分解的第一个因子是d，那么剩下的部分x/d的分解方案数是f(x/d)。把第一个因子d从2到x枚举，把所有f(x/d)加起来，就得到f(x)。特别地定义f(1)=1，表示空分解只有1种，这样第一个因子就是x本身的方案也会被计入，对应N=N这一种。

第三步，只考虑N的因数。 因为分解出来的每个因子都是N的因数，x/d也一定是N的因数，所以只需要枚举N的所有因数，按从小到大排序，再按顺序递推f值。N最大接近20亿，从小到大枚举i，只要i×i不超过N，就把i和N/i都加入因数列表。

第四步，递推计算。 对每个因数x，枚举比它小的因数d（从2开始），如果d能整除x，就累加f(x/d)。因数个数很少（最多约1500个），直接线性查找x/d在因数列表中的位置即可。例如N=12时，因数有1、2、3、4、6、12，递推得到f(12)=8，与样例一致。

第五步，输出答案。 排序后最大的因数就是N本身，输出f(N)即可。注意方案数可能很大，用long long存储。

参考代码

// 因式分解：枚举N的所有因数，按因数从小到大递推分解方案数
#include <iostream>
#include <algorithm>
using namespace std;
long long divs[5000];
long long f[5000];
int dcnt;
int main() {
    long long n;
    cin >> n;
    // 枚举n的所有因数
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divs[dcnt++] = i;
            if (i != n / i) divs[dcnt++] = n / i;
        }
    }
    sort(divs, divs + dcnt);
    f[0] = 1; // 因数1的分解方案只有1种：空
    for (int i = 1; i < dcnt; i++) {
        long long x = divs[i];
        long long cnt = 0;
        // 枚举x的因数d(从2开始)，第一个因子取d，剩下x/d的方案累加
        for (int j = 1; j <= i; j++) {
            long long d = divs[j];
            if (d >= 2 && x % d == 0) {
                long long q = x / d;
                int k = 0;
                while (divs[k] != q) k++; // 因数个数少，线性查找即可
                cnt += f[k];
            }
        }
        f[i] = cnt;
    }
    cout << f[dcnt - 1] << endl; // 最大的因数就是n本身
    return 0;
}

复杂度分析

枚举N的因数需要循环到根号N，约44721次。设N的因数个数为D，递推部分需要O(D²)的时间，D最多约1500，总复杂度非常小。空间上只存D个因数，空间复杂度O(D)。即使N接近20亿，程序也能在瞬间完成，不会超时。