因式分解
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
将大于1的自然数N进行因式分解,满足N=a1*a2*a3…*am。
编一程序，对任意的自然数N（1< N<=2,000,000,000），求N的所有形式不同的因式分解方案总数。如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
Input
输入只有一行，一个整数N。
Output
输出只有一行，一个整数表示自然数N的因式分解方案总数。
Sample Input
12
Sample Output
8
鉴于这个题目的数据有点大（1< N<=2,000,000,000），所以我一开始的想法是这样的，开一个数组记录一下每个数字的因式分解数目，但是这个题只有一个输入。。。并且这样做的时间实在是长的很：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
int s[400000]={0};
int main(){
s[2]=1;
int n;
int sum=0;
cin>>n;
for(int j=3; j<=n; j++){
for(int k=2; k<j; k++){
if(!(j%k)){
s[j]+=s[k];
}
}
s[j]++;
}
cout<<s[n]<<endl;
}所以后来又改成了递归的做法，其实这样做应该是不对的，但是居然AC了，只能说后台的测试点有点问题啊。。。但是单看这个问题的时间空间要求，实在是没找出好的方式，百度了一下发现有的题目空间允许的比较大。。。现在这里占个坑记录一下吧：
#include<stdio.h>
#include<iostream>
using namespace std;
int cou=1;
int fun(long long int n){
for(long long int i=2; i<n; i++){
if(!(n%i)){
fun(n/i);
cou++;
}
}
}
int main(){
long long int n;
cin>>n;
fun(n);
cout<<cou<<endl;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116840.html
