练83.4 分解因数

解题思路

递归count(rem,low)表示剩余乘积rem、下一因子至少low的分解数。rem本身作为最后一个因子贡献1，再枚举low～√rem可整除的d，递归(rem/d,d)。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

非降因子顺序通过low约束，避免2×10与10×2重复；单因子a也计。

复杂度

搜索状态依因子分解数而定，单状态至多O(√a)枚举；递归深度O(log a)。

参考代码（C++11）

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

long long ways(int rem, int low) {
    long long ans = 1;
    for (int d = low; d <= rem / d; d++)
        if (rem % d == 0)
            ans += ways(rem / d, d);
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        cout << ways(a, 2) << "\n";
    }
    return 0;
}