A26532. 分解因数给出一个正整数 a， 要求分解成若干个正整数的乘积， 即 a = a1 * a2 * a3 * ... * an， 并且 1 < a1 ≤ a2 ≤ a3 ≤ ... ≤ an， 问这样的分解的种数有多少。 注意到 a = a 也是一种分解。输入第 1 行是测试数据的组数 n， 后面跟着 n 行输入。每组测试数据占 1 行， 包括一个正整数 a (1 < a < 32768)输出n 行，…
填空题
中等
知识点
题目描述
分解因数
给出一个正整数 a， 要求分解成若干个正整数的乘积， 即 a = a1 * a2 * a3 * ... * an， 并且 1 < a1 ≤ a2 ≤ a3 ≤ ... ≤ an， 问这样的分解的种数有多少。 注意到 a = a 也是一种分解。
输入
第 1 行是测试数据的组数 n， 后面跟着 n 行输入。每组测试数据占 1 行， 包括一个正整数 a (1 < a < 32768)
输出
n 行， 每行输出对应一个输入。 输出应是一个正整数， 指明满足要求的分解的种数
样例输入
2
2
20样例输出
1
4参考答案
#include <bits/stdc++.h>
using namespace std;
//返回数字k分解成由大于等于st的因数乘积的形式的分解方案数
int solve(int k, int st)
{
if(k == 1)//k为1表示分解结束，形成1种方案
return 1;
int ct = 0;
for(int i = st; i <= k; ++i)
{
if(k%i == 0)
ct += solve(k/i, i);//分解方案增加：将k/i分解成因数最小为i的分解方案数。
}
return ct;
}
int main()
{
int n, a;
cin >> n;
while(n--)
{
cin >> a;
cout << solve(a, 2) << endl;//分解数字a，因数大于等于2
}
return 0;
}
上一题
下一题