P4743 分解因数（提高）

解题思路

第一步：看懂题目。 把一个正整数 a 分解成若干个正整数的乘积，要求这些因数从小到大排列（后面的不小于前面的），问一共有多少种分解方法。注意“a=a”也算一种分解，也就是不分解的情况也算。

第二步：先看个例子。 a=20 时，分解方法有：20、2×10、4×5、2×2×5，一共 4 种。

第三步：设计递归函数。 设函数 countWays(num, minFactor) 表示：把 num 分解成乘积，并且最小的因数不小于 minFactor，一共有多少种方法。首先，把 num 自己当作一种分解（先算 1 种）。然后从 factor=minFactor 开始，一个个试 factor 能不能整除 num：如果能整除，说明可以取 factor 作为下一个因数，剩下的 num/factor 还要继续分解，而且剩下的因数不能小于 factor，所以再加上 countWays(num/factor, factor)。

第四步：用例子验证递归过程。 countWays(20,2)：先算上 20 自己；factor=2 能整除，countWays(10,2)=2（10 和 2×5）；factor=3 不能整除；factor=4 能整除，countWays(5,4)=1（5 自己）。总和 1+2+1=4，正确。

第五步：为什么循环到 factor×factor ≤ num 就够了？ 因为因数是从小到大排的，如果最小的因数 factor 大于 √num，那 num/factor 就小于 factor，不可能再分解成不小于 factor 的因数，只有 num 自己这一种情况，而这种情况已经用“先算上 1”表示了。

第六步：注意边界情况。 a=2 是质数，countWays(2,2)=1，只有“2”这一种分解。a<32768，递归层数很少，每组数据独立计算。

参考代码

// 分解因数：递归统计把a分解成非降序列乘积的种数
#include <iostream>

int countWays(int num, int minFactor) {
    int ways = 1;                          // 只分一个数num本身也算一种
    for (int factor = minFactor; factor * factor <= num; factor++) { // factor是下一个因数，不小于minFactor
        if (num % factor == 0) ways += countWays(num / factor, factor);
    }
    return ways;
}

int main() {
    int cnt;
    std::cin >> cnt;
    while (cnt--) {
        int a;
        std::cin >> a;
        std::cout << countWays(a, 2) << "\n";
    }
    return 0;
}

复杂度分析

对每个 num，循环从 minFactor 试到 √num。a 最大是 32767，√a 大约 181，循环次数很少。最坏情况下递归层数就是因数分解的层数，比如一直除以 2，最多十几层。所以每组数据的时间复杂度约为 O(√a × 层数)，几乎可以看成常数级。空间上递归深度小，是 O(log a)。cnt 组数据互不影响，整体非常快。