OpenJudge 2952 循环数 C++

链接地址:

http://bailian.openjudge.cn/practice/2952/

题目:

总时间限制:
1000ms
内存限制:
65536kB
描述
n 位的一个整数是循环数(cyclic)的条件是:当用一个 1 到 n 之间的整数去乘它时, 会得到一个将原来的数首尾相接循环移动若干数字再在某处断开而得到的数字。也就是说,如果把原来的数字和新的数字都首尾相接,他们得到的环是相同的。只是 两个数的起始数字不一定相同。例如,数字 142857 是循环数,因为:
142857 *1 = 142857
142857 *2 = 285714
142857 *3 = 428571
142857 *4 = 571428
142857 *5 = 714285
142857 *6 = 857142



输入
写一个程序确定给定的数是否是循环数。输入包括多个长度为 2 位到 60 位的整数。(注意,先导的0也是合理的输入不应该被忽略,例如 "01"是 2 位数,"1" 是 1 位数。)
输出
对于每一个输入的整数,输出一行表明它是否是循环数。

样例输入
142857
142856
142858
01
0588235294117647


样例输出
142857 is cyclic
142856 is not cyclic
142858 is not cyclic
01 is not cyclic
0588235294117647 is cyclic

来源
1047

思路:

输入包括多个长度为 2 位到 60 位的整数,所以不能直接使用int保存
因为要遍历每次乘法可改为每次加上原来的是数,乘法变成加法
比较使用循环比较

所以这个的重点是大数加法

代码:

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 string sum(string s1,string s2)
 6 {
 7     if(s1.length()<s2.length())
 8     {
 9         string temp=s1;
10         s1=s2;
11         s2=temp;
12     }
13     int i,j;
14     for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)
15     {
16         s1[i]=char(s1[i]+(j>=0?s2[j]-0:0));   //注意细节
17         if(s1[i]-0>=10)
18         {
19             s1[i]=char((s1[i]-0)%10+0);
20             if(i) s1[i-1]++;
21             else s1=1+s1;
22         }
23     }
24     return s1;
25 }
26 
27 int main()
28 {
29     string str;
30     string::size_type i,j,size_str;
31     while(cin>>str)
32     {
33         string str1(str);
34         size_str= str.size();
35         while(--size_str)
36         {
37             str1 = sum(str1,str);
38             if(str1.size() != str.size()) break;
39             for(i = 0; i < str.size(); i++)
40             {
41                 for(j = 0; j < str1.size(); j++)
42                 {
43                     if(str1[j] != str[(i + j) % str.size()]) break;
44                 }
45                 if(j >= str1.size()) break;
46             }
47             if(i >= str.size()) break;
48         }
49         if(size_str) cout<<str<<" is not cyclic"<<endl;
50         else cout<<str<<" is cyclic"<<endl;
51     }
52     return 0;
53 }

参考资料:

http://blog.csdn.net/hp_justdoit/article/details/8297003

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。