题解 P1217 【[USACO1.5]回文质数 Prime Palindromes】

博客已挂 # 回文质数2.0 Plus 此次更新,对普通做法进行了更鲜明的阐述。 ## 首先是最快速，也是oi中的得分神器 >打表法就是将题目中需要的答案集合提前算出来，存到代码里，根据题目所需取答案，这种方法通常只需要将程序挂着，在表打完后进行加工，最终取答案程序时间复杂度为O(1)，空间复杂度为O(n)(n为答案规模)； ——沃兹·基朔德 思路由来：当我拿到这道题时，首先想到的思路就是循规蹈矩的做，结果当然T了，我看题解时突发奇想。既然答案是有限的，何不打表做呢? #### 首先是回文数的判断方法 ``` bool pd_h(int x) { int y=x,num=0;//int y=x,防止x被改变 while (y!=0) { num=num*10+y%10;//上一次数字的记录进位再加上下一位数 y/=10; } if (num==x) return 1; else return 0; } ``` 很好理解吧，将输入的x一位一位的存到另一个数中，然后作比。 #### 判断质数方法主要有三种，这里我先介绍第一种，也是最简单的一种，其他两种我会在下文提到。 **在这里首先要知道：1.偶数位数回文数（除11）必定不是质数（自行百度），所以只要运行到10000000。2.偶数肯定不是质数。这样至少排除一半多的数据量。3，你回文数已经判断出来了，在此中判断即可。** ``` bool Prime(int x){ int jl=0; int w=0; int k=x;//防止x的值改变 while(k) { w++; k/=10; } if(w%2==0||x%2==0) return 0; for(int k=2;k<=sqrt(x);k++) if(x%k==0) jl=1; if(jl==0) return 1; else return 0; } ``` 然后就让程序挂着，记得加freopen保存结果，最后将表存入主程序。 ``` #include<bits/stdc++.h>//万能头文件 using namespace std; int a[5960]={//防止作弊不给予具体显示}; int main(){ int s,e; cin>>s>>e; int j=0; for(j;;j++) { if(j>5959) break; if(a[j]>=s&&a[j]<=e) cout<<a[j]<<endl; if(a[j]>e) break; if(a[j]<s) continue; } return 0; } ``` 以下是部分问题。 ### Q1 "打表无耻"吗？是不是作弊？ **Answer** 打表只是众多做题方法中的一个，并不能说用这种方法就无耻。不然，你在蓝翔笑他无耻，他在五道口职业技术学院不愿说话。 打表并不是作弊啊，（我凭本事打的表，我凭时间打的表，凭什么说我作弊？）打表是正常的做题方法，并无二异； ### Q2 挂了多久？是不是很慢 **Answer** 因此我还专门做了一个实验。 测试指令 g++ -o pd pd.cpp 测试计算机 - 处理器：Intel Core T6600 2.20Ghz - RAM：2.00GB - 系统: 自装32位win8 对，这是10年前的老古董。那他跑这个程序花了多长时间呢？ - 测试1:2.458s - 测试2:2.197s - 测试3:2.475s 这几秒在提交的代码中过不去，但可以在做题的时候挂着，如此简单的AC啊。 ## 接下来就是正常的做法了 首先介绍一种筛取质数的方法——埃拉托斯特尼筛法 >埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。——百度百科 在筛质数时，我们会发现，筛去2后，2的倍数4、6、8等一定不是素数;筛去3后，3的倍数6、9、12等一定不是倍数。简单模拟这个过程如下  >图引于Wikipedia 这个方法的代码也很好写 ``` const int MAXN = 1000000； void Prime() { for (int i=0; i<MAXN; i++) prime[i]=1; //先把每个数都定义为合数 prime[0]=prime[1]=0; for (int i=2; i<MAXN; i++) { if (!prime[i]) continue; for (int j=i*2; j<MAXN; j+=i) prime[j] = 0; //将i的倍数标记为合数 } } ``` 埃拉托斯特尼筛法的时间复杂度是O(n*lglgn)，使用这种方法做这道题，应该是可以AC（没试过，逃~） 那么第三种算法是最难理解的，同时也是最快的线性筛法，时间复杂度接近O(n)。这种筛法容易理解，代码不容易看懂。 看上面的动图，你会发现，6同时被2和3各筛了一次。它在计算时就被访问了两次,这样会导致效率低下。 原理：对于任意合数，必定可以有最小质因子乘以最大因子的分解方式。因此，对于每个合数，只要用最大因子筛一遍，枚举时只要枚举最小质因子即可。 ``` int vis[MAXN]; int prime[MAXN]; void Prime() { int cnt=0; for(int i=2;i<=n;i++) { if(!vis[i]) prime[cnt++]=i; for(int j=0;j<cnt&&i*prime[j]<=n;j++) { vis[i*prime[j]]=i; if(i%prime[j]==0) break; } } } ``` 如有想深入了解或是看了本蒟蒻题解仍不了解线性筛的，下面是温馨提醒 >本小组已经与百度公司达成协议，以后有不会的题可以上百度搜索。 下面是线性筛的AC枚举代码 ``` #include<iostream> #include<cstdio> #define MAXN 10000005 using namespace std; int prime[MAXN]; bool pp[MAXN]; int vis[MAXN]; bool pd_h(int x) { int y=x,num=0;//int y=x,防止x被改变 while (y!=0) { num=num*10+y%10;//上一次数字的记录进位再加上下一位数 y/=10; } if (num==x) return 1; else return 0; } int main() { int a,b; cin>>a>>b; int cnt=0; if(b>10000000) b=10000000; for(int i=2;i<=b;i++) { if(!vis[i]) prime[cnt++]=i,pp[i]=1; for(int j=0;j<cnt&&i*prime[j]<=b;j++) { vis[i*prime[j]]=i; if(i%prime[j]==0) break; } } for(int i=a;i<=b;i++) { if(i>10000000) break; if(pd_h(i)&&pp[i]) printf("%d\n",i); } } ``` 好啦。这篇题解主要是给大家介绍了一下打表法的实际应用。当然，它也有不足，当数据规模过大，打表不仅慢，而且内存会爆。 所以各位小可爱们，平常还是要好好学习优化。 ## 再有，我不是dalao。但你看我这么用心，不给我个赞再走嘛？