整数因子分解问题
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^题目描述
大于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，n≤1200000000。
输出
将计算出的不同的分解式数输出。
示例输入
示例输出
数据范围不言而喻，递归囧对超时。
因为当n=12时， 值之所以为8就是他的因子的作用。故对因子分析。
一般的，较大数为某个更大数的因子，比这个较大数小的因子也可能是这个较大数的因子，如果是那么这个数的所有因子也是较大因子的因子（比较绕），
所以再枚举比当前因子小的因子,那么就dp[j]+=dp[i]，
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int permutation[1<<20],s,ans;
int dp[1<<20];
void f(int n)
{
for(int i=1;i*i<=n;i++)
{
if( !(n%i) )
{
int p=n/i;
if(n/i!=i)
{
permutation[s++]=n/i;
permutation[s++]=i;
}
else
permutation[s++]=n/i;
}
}
}
void solo(int s)
{
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<s;i++)
{
for(int j=0;j<i;j++)
{
if(permutation[i]%permutation[j]==0)
{
dp[i]+=dp[j];
}
}
}
}
int main()
{
int n,i;
ios::sync_with_stdio(false);
while(cin>>n)
{
s=0;ans=0;
f(n);
sort(permutation,permutation+s);
solo(s);
cout<<dp[s-1]<<endl;
}
return 0;
}
