1200：分解因数
时间限制: 1000 ms 内存限制: 65536 KB
提交数:28701 通过数: 16200
【题目描述】
给出一个正整数a𝑎，要求分解成若干个正整数的乘积，即a=a1×a2×a3×...×an，并且1<a1≤a2≤a3≤...≤an，问这样的分解的种数有多少。注意到a=a也是一种分解。
【输入】
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占11行，包括一个正整数a(1<a<32768)。
【输出】
n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数。
【输入样例】
2
2
20
【输出样例】
1
4
【原题链接】信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
https://ybt.ssoier.cn/problem_show.php?pid=1200注意：a=a也是一种分解，统计时初始化为1（cnt=1)。
#include <iostream>
using namespace std;
int n, a, cnt;
void f(int a, int k) {
if (k >= a) return; //满足因子大于a
for (int i = k; i * i <= a; i++) { //从k开始分解
if (a % i == 0) { //能够整除，是因子
cnt++; //加1
f(a / i, i); //继续分解
}
}
}
int main() {
cin >> n;
while (n--) {
cin >> a; //对a分解
cnt = 1; //自己本身也是一种分解方式
f(a, 2); //a分解从2开始
cout << cnt << endl;
}
return 0;
}
