- 因式分解
XJOI - 题目ID：8740100分
最新提交：
Wrong Answer
12 分
历史最高：
Time Limit Exceeded
62 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
题目描述
将大于的自然数
n 进行因式分解
编一程序，对任意的自然数
1<n≤2000000000求
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
输入格式
一个整数
n
输出格式
一个整数
m，代表不同的因式分解的方案总数。
样例数据
input
12
output
8
数据规模与约定
时间限制：
1s
空间限制：
256MB
TLE62:
#include<bits/stdc++.h>
using namespace std;
int ans=0,n;
void dfs(int x){
if(x==1){
ans++;
cout<<endl;
return ;
}
for(int i=2;i<=x;i++){
if(x%i==0){
// cout<<x/i<<" ";
dfs(x/i);
}
}
}
int main(){
cin>>n;
dfs(n);
cout<<ans<<endl;
}
WA12:
#include<bits/stdc++.h>
using namespace std;
int ans=0,n;
bool f(int m){
if(m==2){
return true;
}
for(int i=2;i*i<=m;i++){
if(m%i==0) return false;
}
return true;
}
void dfs(int x){
// cout<<x<<" ";
ans++;
if(f(x)){
ans++;
// cout<<endl;
return ;
}
for(int i=2;i*i<=x;i++){
if(x%i==0){
dfs(x/i);
}
}
}
int main(){
cin>>n;
dfs(n);
cout<<ans+1<<endl;
}
