首页 > 代码库 > USACO 1.5 Prime Palindromes
USACO 1.5 Prime Palindromes
Prime Palindromes
The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .
PROGRAM NAME: pprime
INPUT FORMAT
| Line 1: | Two integers, a and b |
SAMPLE INPUT (file pprime.in)
5 500
OUTPUT FORMAT
The list of palindromic primes in numerical order, one per line.
SAMPLE OUTPUT (file pprime.out)
5711101131151181191313353373383
——————————————————————题解
就是枚举回文数然后筛，写了一个logn的筛法（Miller Rabin），结果乘法没开longlong导致wa了一次
枚举素数我手敲了八个循环……后来ac看analysis……只要10-9999然后翻转就行orz我感觉自己真是个辣鸡
而且这位小哥以神一般的数学直觉便判断出任何二倍长的回文数一定是11的倍数，那么我们就不用考虑偶数个的了。小学数学老师你还要我吗要我吗……
这轻描淡写的一句话顶上了我30++行代码orz
那个版权不敢盗，所以不粘别人代码，贴上我易读的代码……以及写的很丑的Miller Rabin（check函数）
1 /* 2 PROB: pprime 3 LANG: C++ 4 ID: jiaqi si 5 */ 6 #include <iostream> 7 #include <string.h> 8 #include <cstdlib> 9 #include <cstdio> 10 #include <algorithm> 11 #include <cstring> 12 #include <vector> 13 #include <ctime> 14 #define ivory 15 #define mo 1000000007 16 #define siji(i,x,y) for(int i=(x);i<=(y);i++) 17 #define gongzi(j,x,y) for(int j=(x);j>=(y);j--) 18 #define xiaosiji(i,x,y) for(int i=(x);i<(y);i++) 19 #define sigongzi(j,x,y) for(int j=(x);j>(y);j--) 20 #define pii pair<int,int> 21 #define fi first 22 #define se second 23 #define mo 1000000007 24 using namespace std; 25 int ans[500005],cnt; 26 int a,b; 27 int mpow(int c,int d,int k) { 28 if(d==1) { 29 return c%k; 30 } 31 else { 32 int tmp=mpow(c,d/2,k)%k; 33 if(d&1) { 34 return 1LL*tmp*tmp%k*c%k; 35 } 36 else { 37 return 1LL*tmp*tmp%k; 38 } 39 } 40 } 41 bool _check(int v,int s,int k) { 42 if(v==1) return true; 43 siji(i,1,s) { 44 if(1LL*v*v%k==1) { 45 if(v%k==k-1){return true;} 46 else return false; 47 } 48 v=1LL*v*v%k; 49 } 50 return false; 51 } 52 bool check(int k) { 53 int tmp=k-1; 54 int s=1; 55 while(tmp%(1<<s)==0) ++s; 56 --s; 57 int d=tmp/(1<<s); 58 int tmp1=mpow(2,d,k); 59 int tmp2=mpow(7,d,k); 60 int tmp3=mpow(61,d,k); 61 bool f=1; 62 if(!_check(tmp1,s,k)) {f=0;} 63 else if(k>7 && (!_check(tmp2,s,k))) {f=0;} 64 else if(k>61 && (!_check(tmp3,s,k))) {f=0;} 65 return f; 66 } 67 int binary(int k){ 68 int l=1,r=cnt; 69 while(l<r) { 70 int mid=(l+r+1)>>1; 71 if(ans[mid]>=k) r=mid-1; 72 else l=mid; 73 } 74 return l; 75 } 76 int main() { 77 #ifdef ivory 78 freopen("pprime.in","r",stdin); 79 freopen("pprime.out","w",stdout); 80 #else 81 //freopen("f1.in","r",stdin); 82 #endif 83 ans[++cnt]=2; 84 siji(i,3,9) { 85 if(i%2!=0 && check(i)) ans[++cnt]=i; 86 } 87 siji(i,1,9) { 88 if(i%2==0)continue; 89 int tmp=i*10+i; 90 if(check(tmp)) ans[++cnt]=tmp; 91 } 92 siji(i,1,9) { 93 if(i%2==0) continue; 94 siji(j,0,9) { 95 int tmp=i*100+j*10+i; 96 if(check(tmp)) ans[++cnt]=tmp; 97 } 98 } 99 siji(i,1,9) {100 if(i%2==0) continue;101 siji(j,0,9) {102 int tmp=i*1000+j*100+j*10+i;103 if(check(tmp)) ans[++cnt]=tmp;104 }105 }106 siji(i,1,9) {107 if(i%2==0) continue;108 siji(j,0,9) {109 siji(k,0,9) {110 int tmp=i*10000+j*1000+k*100+j*10+i;111 if(check(tmp)) ans[++cnt]=tmp;112 }113 }114 }115 siji(i,1,9) {116 if(i%2==0) continue;117 siji(j,0,9) {118 siji(k,0,9) {119 int tmp=i*100000+j*10000+k*1000+k*100+j*10+i;120 if(check(tmp)) ans[++cnt]=tmp;121 }122 }123 }124 siji(i,1,9) {125 if(i%2==0) continue;126 siji(j,0,9) {127 siji(k,0,9) {128 siji(h,0,9) {129 int tmp=i*1000000+j*100000+k*10000+h*1000+k*100+j*10+i;130 if(check(tmp)) ans[++cnt]=tmp;131 }132 133 }134 }135 }136 siji(i,1,9) {137 if(i%2==0) continue;138 siji(j,0,9) {139 siji(k,0,9) {140 siji(h,0,9) {141 int tmp=i*10000000+j*1000000+k*100000+h*10000+h*1000+k*100+j*10+i;142 if(check(tmp)) ans[++cnt]=tmp;143 }144 }145 }146 }147 scanf("%d%d",&a,&b);148 int il=binary(a);149 int ir=binary(b);150 if(ans[ir+1]==b) ir++;151 siji(i,il+1,ir) {152 printf("%d\n",ans[i]);153 }154 }
USACO 1.5 Prime Palindromes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。