2749:分解因數

總時間限制: 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==)return ;
    if(b==)return ;
    if(a%b==)return f(a/b,b)+f(a,b-);
    return f(a,b-);
}
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==&&i<=b/i)  
        {  
            sum++;  
            count(i,b/i);//遞歸計算  
        }  
        if(i>b/i) break;  
    }  
}  
int main()  
{  
    int n;  
    int a;  

    cin >> n;  
    while(n)  
    {  
        sum = ;  
        cin >> a;  
        count(,a);  
        cout<<sum<<endl;  
        n--;  
    }  
    //cout << "Hello world!" << endl;  
    return ;  
}