Caioj 1043:因式分解

这道题我至今为止已经找到了三种做法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
我们可以发现,这不白白搜索两次吗??? 明白着的浪费时间啊 “浪费就是犯罪”–名人名言   我们该怎么办呢? 我们给这个数开个方,然后循环枚举,i与t/i不相同的ans+2,否则+1,就像下面这一段
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

End

]]>

留下评论

电子邮件地址不会被公开。 必填项已用*标注