1219-整数因子分解问题

描述

大于1 的正整数n可以分解为：n=x1*x2*…*xm。 例如，当n=12 时，共有8 种不同的分解式：

12=12；

12=6*2；

12=4*3；

12=3*4；

12=3*2*2；

12=2*6；

12=2*3*2；

12=2*2*3。

对于给定的正整数n，编程计算n共有多少种不同的分解式。

输入

输入的第一行有1个正整数n (1≤n≤2000000000)。

输出

输出计算出的不同的分解式数。

样例输入

12

样例输出

8

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
    int n,a[10000],dp[10000];
    cin>>n;
    int i,j,k;
    k=0;
    for(i=1;i*i<n;i++)
        if(n%i==0)
        {
            a[k++]=i;
            a[k++]=n/i;
        }
    if(i*i==n)
        a[k++]=i;
    sort(a,a+k);
    dp[0]=1;
    for(i=1;i<k;i++)
    {
        dp[i]=0;
        for(j=0;j<i;j++)
            if(a[i]%a[j]==0)
                dp[i]+=dp[j];
    }
    cout<<dp[k-1]<<endl;
    return 0;
}