yzoi1109&&viojs1042最小步数的一点看法——回文数
Description - 问题描述
有一天,雄霸传授本人风神腿法第一式:捕风捉影..............的步法(弟子一:堂主,你大喘气呀。风:你给我闭嘴。)捕风捉影的关键是换气(换不好就会大喘气...)。
使用捕风捉影这一招时并不是每一步都喘气,而是在特定的步数喘气。一般来说功力越高,喘气越稀疏。喘气的步数符合特定规律:第一要是SUSHU(弟子二:哇塞!堂主,你还会鸟语,我好好崇拜你呦!可是SUSHU是什么意思呢?风:笨蛋,那是汉语拼音!)第二要是一个回文数,回文数就是正反念一样的数,如:123321,121,5211314(弟子三:堂主,最后一个好象不是...风:废话,当然不是了,我是考察一下你们的纠错能力!)现在给出两个数M,N(5< =M< N< =100,000,000),你要算出M,N之间需要换气的都有哪几步。(包括M,N)。算出来的可以提升为本堂一级弟子,月薪(1000000000000000000000000000000000000000000 MOD 10 )元。
可能在众位神犇看来这是一道水的不能再水的题目,但我认为还是有必要提一提的。首先,这是一道判断素数+回文数的题,对于回文数,百度的定义是如下的:
1 #include<iostream> 2 using namespace std; 3 bool symm(long m) 4 { 5 long temp = m,n=0; 6 while (temp) 7 { 8 n = n*10+temp%10; 9 temp = temp/10; 10 } 11 return (m == n); 12 } 13 int main(int argc, _TCHAR* argv[]) 14 { 15 long m; 16 cout<<"请输入一个整数:"; 17 cin>>m; 18 cout<<"输入了"<<symm(m)<<"个回文数!"; 19 return 0; 20 }
个人认为,对于回文数的判断基本可用该法进行。但同时亦可以string读入,用s.size()判断是奇是偶,后再从中向左向右搜索即可。
我的代码:
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 const int maxn=3000000; 5 //int p[maxn]; 6 int m,n; 7 //int sum=0; 8 //void make() 9 //{ 10 // p[1]=1; 11 // for(int i=2;i<=sqrt(maxn);i++) 12 // if(p[i]==0) 13 // for(int j=2;j<=sqrt(maxn)/i;j++) 14 // p[i*j]=1; 15 //} 16 bool pd_1(int m) 17 { 18 int temp=m,n=0; 19 while(temp) 20 { 21 n=n*10+temp%10; 22 temp/=10; 23 } 24 return (m==n); 25 } 26 //bool pd_2(int m) 27 //{ 28 // if(p[m]) 29 // return false; 30 // else 31 // return true; 32 //} 33 bool pd_2(int m) 34 { 35 for(int i=2;i<=sqrt(m);i++) 36 { 37 if(m%i==0) 38 return false; 39 } 40 return true; 41 } 42 bool pd_3(int m) 43 { 44 int k=m%10; 45 if((k==2||k==4||k==5||k==6||k==8||k==0)&&(m/10>=1)) 46 return false; 47 else 48 return true; 49 } 50 int main() 51 { 52 // make(); 53 cin>>m>>n; 54 if (n>10000000) 55 n=10000000; 56 for(int i=m;i<=n;i++) 57 { 58 if(pd_1(i)&&pd_3(i)) 59 if(pd_2(i)) 60 cout<<i<<endl; 61 } 62 return 0; 63 } 64 /************************************************************** 65 Problem: 1109 66 User: lwq 67 Language: C++ 68 Result: Accepted 69 Time:559 ms 70 Memory:1320 kb 71 ****************************************************************/
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。