OpenJudge 2952 循环数 C++

浏览数：68 / 时间：2015年06月09日

链接地址：

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 }