这道题我至今为止已经找到了三种做法2333333,也是够了
如何思考
题目题面:[http://caioj.cn/problem.php?id=1043]这种题目一看就是搜索=.=,然后,我们看一下数据样例
12=12 12=62 12=43 12=34 12=322 12=26 12=232 12=223等一下12=12???12=34与12=43?? 是的他自己也算一种,并且,两个因数交换后也算一种. 好了让我们开始代码
第一回:爆搜
状态: 20%TLE
#include <cstdio>
#include <cmath>
using namespace std;
int n,cnt;// n 读入的数字; cnt 统计和
// zs(int k) 判断 k 是否为质数
// 不解释
bool zs(int k){
int temp=sqrt(k);
for(int i=2;i<=temp;i++){
if(k%i==0) return false;
}
return true;
}
// dfs(int deep) 深搜; deep 当前值
void dfs(int deep){
cnt++;//每搜到一个就一定时一种情况
if(zs(deep)) return ;//是指数就没必要搜了
for(int i=2;i<deep;i++){// 小于deep 的每个都试一次
if(deep%i==0){// 如果能整除,继续搜索
dfs(deep/i);
}
}
}
int main(){
scanf("%d",&n);//读入
dfs(n);//开始搜索
printf("%d",cnt);//输出
}
显然这道题目不会这么简单=.=,果然超时了2333
第二回:打个质数表
显然上面这么搜索盲目又耗时间,我们还不如先存下来可以被 n 整除的数,然后从 1 往上一个个找,这样看来会好多 状态: AC 时间:496 ms 内存:1176 kb
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[11000],len;
void fz(int x){
int t=int(sqrt(double(x+1)));
for (int i=2;i<=t;i++){
if (x%i==0){
a[++len]=i;
if (x/i!=i)a[++len]=x/i;
}
}
}
int n,ans;
void dfs(int d){
ans++;
for (int i=1;i<=len;i++){
if (d*a[i]>n) break;//如果因子比n大则直接跳出
if (n%(d*a[i])==0&&n!=d*a[i]){
dfs(d*a[i]);
}
}
}
int main(){
scanf("%d",&n);
len=0;fz(n);
sort(a+1,a+len+1);//加了一步排序
ans=0;dfs(1);
printf("%d\n",ans);
return 0;
}
第三回:对称性剪枝
这个玩意儿~是金哥讲的,金哥果然厉害我们来看一下面两个:这不废话
12=3*4
12=4*3
我们可以发现,这不白白搜索两次吗???
明白着的浪费时间啊 void search(int t){
int temp=sqrt(t);//开方
for(int i=2;i<=temp;i++){//循环枚举
if(t%i==0){//能否整除
if(i!=(t/i)){ //不相同说明可以交换,ans+2,两边都要搜
ans+=2;
search(t/i);
search(i);
}
else{ //否则ans+1,只搜一边
ans++;
search(t/i);
}
}
}
}
上述代码 状态: AC 时间: 212 ms 内存: 1128 kb