当前位置 博文首页 > pzkcsdn的博客:整数因子分解问题
Problem Description
大于1的正整数n可以分解为:n=x1x2…xm。例如,当n=12 时,共有8 种不同的分解式:
12=12;
12=62;
12=43;
12=34;
12=322;
12=26;
12=232;
12=22*3。
对于给定的正整数n,计算n共有多少种不同的分解式。
Input
输入数据只有一行,有1个正整数n (1≤n≤2000000000)。
Output
将计算出的不同的分解式数输出。
Sample Input
12
Sample Output
8
#include <bits/stdc++.h>
using namespace std;
int a[200000],dp[200000];//dp: 第i个约数能够再进行分解的式子个数
int f(int n){
int i,j, k = 0;
for(i = 2; i<=sqrt(n); i++)//计算出n的所有约数并存放在数组a中
{
if(n%i==0){
a[k++] = i;
a[k++] = n/i;
}
}
a[k++] = n;
sort(a,a+k);
for(i = 0; i<k; i++){
dp[i] = 1;//每个约数都有它本身自己一个分解式
for(j = 0; j<i; j++){
if(a[i]%a[j]==0)
{
dp[i] += dp[j];//在第i个约数分解式个数的基础上加上第j个约数的分解式个数
}
}
}
return dp[k-1];
}
int main()
{
int n;
cin>>n;
cout<<f(n)<<endl;
return 0;
}