首页 > 代码库 > HDU 1431
HDU 1431
可以先找出回文数,再用素数测试来判是否为素数即可。
打回文数时,因为左右对称,可以只枚举后半部,然后通过逆转得到前半部分。
#include <iostream>#include <cstdio>#include <time.h>#include <stdlib.h>#include <algorithm>using namespace std;const int Max=200000;int huiwen[Max],answer[Max];int htop;int anter(int i){ int ans=1; while(i){ ans*=10; i--; } return ans;}int gethuiwen(int t,int p){ int ans=0; while(p>1){ ans*=10; ans+=(t%10); p/=10; t/=10; } return ans;}void for_back(){ htop=0; for(int i=5;i<=9;i++) huiwen[htop++]=i; for(int i=2;i<=8;i++){ int p=anter(i/2); // cout<<p<<endl; if(i%2){ for(int k=0;k<=9;k++){ for(int t=0;t<p;t++){ if(t%10==0) continue; int tail=gethuiwen(t,p); // cout<<tail<<‘ ‘<<t<<endl; huiwen[htop++]=(tail*10+k)*p+t; } } } else{ for(int t=0;t<p;t++){ if(t%10==0) continue; int tail=gethuiwen(t,p); huiwen[htop++]=(tail)*p+t; } } }// cout<<huiwen[htop-1]<<endl;// for(int i=10;i<=50;i++)// cout<<huiwen[i]<<endl;}long long random(long long n){ return (long long )((double)rand()/RAND_MAX*n+0.5);}long long quick(long long a,long long k,long long m){ long long ans=1; while(k){ if(k&1){ ans=ans*a%m; } k>>=1; a=a*a%m; } return ans;}bool Miller_Rabin(long long k){ for(int i=1;i<=50;i++){ long long a=random(k-2)+1; if(quick(a,k-1,k)!=1) return false; } return true;}int main(){ srand(time(0)); for_back(); int tmp=htop; htop=0;// cout<<huiwen[tmp-1]<<endl; for(int i=0;i<tmp;i++){ // cout<<"NO"<<endl; if(Miller_Rabin(huiwen[i])){ // cout<<"YES"<<endl; // break; huiwen[htop++]=huiwen[i]; } } int a,b,ast; while(scanf("%d%d",&a,&b)!=EOF){ ast=0; for(int i=0;i<htop;i++){ if(huiwen[i]>=a&&huiwen[i]<=b) answer[ast++]=huiwen[i]; } sort(answer,answer+ast); for(int i=0;i<ast;i++) printf("%d\n",answer[i]); cout<<endl; } return 0;}
HDU 1431
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。