总时间限制: 1000ms 内存限制: 65536kB 描述 给出一个正整数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
题解：开始自己想的时候，以为a很大，不能用递归，然后就想用数组存储所有数的分解种数想找规律，像动态规划那样，结果发现会有很多重复的情况没法计算。然后从网上找到下面两个解法，都是用的递归，很简洁，第一个用的方法就是程序设计导引上面的简单整数划分的方法，不同点就是返回条件m和i都是等于1的时候返回，以及if里面是可以整除的时候就调用。
#include<iostream> using namespace std; //http://bailian.openjudge.cn/practice/2749/ //不是很明白这个递归的意思，但是真的好简单啊 int n,x; int f(int a,int b){ if(a==1)return 1; if(b==1)return 0; if(a%b==0)return f(a/b,b)+f(a,b-1); return f(a,b-1); } int main(){ cin>>n; while(n--){ cin>>x; int res=f(x,x); cout<<res<<endl; } } #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <queue> #include <algorithm> using namespace std; int sum; void count(int a,int b) { for(int i=a;i<b;i++) { if(b%i==0&&i<=b/i) { sum++; count(i,b/i);//递归计算 } if(i>b/i) break; } } int main() { int n; int a; cin >> n; while(n) { sum = 1; cin >> a; count(2,a); cout<<sum<<endl; n--; } //cout << "Hello world!" << endl; return 0; }