标签：素数表

这道题我至今为止已经找到了三种做法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

]]>