P4751 因数分解（基础）

解题思路

这道题要我们把一个正整数 a 拆成若干个数的乘积，而且拆出来的因子要从小到大排好（a1 ≤ a2 ≤ ... ≤ an），每个因子都要大于 1，问一共有多少种拆法。注意，"a = a"这样只写一个数也算一种拆法。

第一步，先看一个例子，理解"有多少种拆法"。 比如 a = 24 时，一共有 7 种拆法：

1. 24
2. 2 × 12
3. 2 × 2 × 6
4. 2 × 2 × 2 × 3
5. 2 × 3 × 4
6. 3 × 8
7. 4 × 6

注意每种拆法里的因子都必须从小到大，不能出现 2 × 4 × 3 这种乱序的写法。

第二步，设计递归函数，明白为什么要带两个参数。 我们规定一个递归函数 countWays(n, p)，表示"把 n 拆成若干个都不小于 p 的因子，一共有多少种拆法"。为什么要带 p 这个参数？因为题目要求因子从小到大，所以每次选的第一个因子不能小于上一个因子，p 就是"下一个因子至少得这么大"的意思。一开始整个数没有任何限制，只要大于 1 就行，所以第一次调用时 p 取 2。

第三步，写出函数的算法。 函数怎么算？分两种情况来想：

• 第一种：不拆，直接把 n 写出来，这算 1 种（就是题目里说的 a = a）。
• 第二种：从 i = p 开始，一个一个试，只要 i 能整除 n（n % i == 0），就让 i 当第一个因子，剩下的 n / i 继续递归分解，不过后面的因子都要不小于 i，所以调用 countWays(n / i, i)。

把所有情况加在一起，就是答案。

第四步，想想循环为什么只用试到 i × i ≤ n。 因为如果 i 是第一个因子，那么剩下的乘积是 n / i，为了保持从小到大的顺序，必须 i ≤ n / i，也就是 i ≤ √n。这样既不会漏掉情况，也能少算很多。

第五步，讲清楚边界情况。 如果找不到任何大于等于 p 的因子，那只有"n 本身"这一种拆法，函数就返回 1，不会死循环。

第六步，看看数据范围够不够用。 a 最大接近 32768，分解过程全都是整数运算，中间结果不会超过 a 本身，所以用 int 就足够，不用担心溢出。

参考代码

// 因数分解：把正整数inputNumber分解成a1*a2*...*an（1<a1<=a2<=...），求分解种数
#include <iostream>
using namespace std;

// 把num分解成因子都不小于minFactor的乘积，返回分解种数（含num本身这一种）
int countWays(int num, int minFactor) {
    int totalWays = 1;                          // 单独一个num也算一种分解
    for (int factor = minFactor; factor * factor <= num; factor++) {
        if (num % factor == 0) {                // factor能整除num，可作为第一个因子
            // 剩下的num/factor继续分解，且后面的因子都要不小于factor
            totalWays += countWays(num / factor, factor);
        }
    }
    return totalWays;
}

int main() {
    int inputNumber;
    cin >> inputNumber;
    // 第一个因子从2开始，保证 a1 > 1
    cout << countWays(inputNumber, 2) << endl;
    return 0;
}

复杂度分析

每次递归都要从 p 试到 √n，尝试的因子个数大约是 √n 个。递归的层数最多是 log₂a（因为每次都至少除以 2），所以总的时间大约为 O(√a × log a) 量级。a 最大接近 32768，√32768 ≈ 181，运算次数很少，瞬间就能算完。递归使用的栈深度是 log₂a 层，空间 O(log a)，非常小。这样我们就能轻松数出所有满足条件的分解种数啦。