1069. 分解因数 _{(Standard IO)}

时间限制:

1000 ms  空间限制: 262144 KB  具体限制 

题目描述

给出一个正整数a,要求分解成若干个正整数的乘积，即a=a1*a2*a3*...*an，并且1<a1<=a2<=a3<=...<=an，问这样的分解方案有多少种。注意a=a也是一种分解。

输入

第一行是测试数据的组数n，后面n行，每行包括一个正整数a(1<a<32768)。

输出

N行，每行输出一个个正整数，表示分解方案数。

样例输入

2220

样例输出

14

数据范围限制

1<a<32768

 

分析：数据范围比较小，递归来做。

 

#include
      
       int ans;void f(int n,int i){    if(n==1) {ans++;return;}    while(i<=n)    {        if(n%i==0) f(n/i,i);        i++;    }}int main(){    int T,N;    scanf("%d",&T);    while(T--)    {        scanf("%d",&N);        ans=0;        for(int i=2;i<=N;i++)            if(N%i==0) f(N/i,i);        //a=a1*a2*a3*...*an,枚举a1从小到大         printf("%d\n",ans);    }    return 0;}