POJ1047RoundandRoundWeGo

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

题目大意：

　　有一些整数具有这样的性质：它的位数为n,把它和1到n的任意一个整数相乘结果的数字会是原数字的一个“环”。说起来比较抽象，观察一下下面的例子就明白了。将原数字首尾相接产生的环与将相乘结果的数字收尾相接产生的环是一样的。

　　142857 *1 = 142857
　　142857 *2 = 285714
　　142857 *3 = 428571
　　142857 *4 = 571428
　　142857 *5 = 714285
　　142857 *6 = 857142

输入：每行一个给定的整数，前置的0不可忽略，例如01和1被视为是不同的数字。

输出：判断每个数是否符合上面的性质，是输出 n is cyclic, 否则输出 n is not cyclic.

Sample Input

142857
142856
142858
01
0588235294117647

Sample Output

142857 is cyclic
142856 is not cyclic
142858 is not cyclic
01 is not cyclic
0588235294117647 is cyclic

此题用暴力即可解决。

 1 //////////////////////////////////////////////////////////////////////////
 2 //        POJ1047 Round and Round We Go
 3 //        Memory: 180K        Time: 0MS
 4 //        Language: C++        Result: Accepted
 5 //////////////////////////////////////////////////////////////////////////
 6 
 7 #include <iostream>
 8 #include <cstring>
 9 
10 using namespace std;
11 
12 int n;
13 char num[61];
14 char temp[61];
15 
16 //比较乘法结果数字是否符合要求
17 bool compare() {
18     for (int i = 0; i < n; ++i) {
19         bool flag = true;
20         for (int j = 0; j < n; ++j) {
21             if (temp[j] != num[(i + j) % n]) {
22                 flag = false;
23                 break;
24             }
25         }
26         if (flag == true) return true;
27     }
28     return false;
29 }
30 
31 int main(void) {
32     while (cin >> num) {
33         n = strlen(num);
34         bool flag = true;
35         
36         //计算大数乘法
37         for (int k = 2; k <= n; ++k) {
38             memset(temp, '0', sizeof(temp));
39             for (int i = n - 1; i > 0; --i) {
40                 int s = temp[i] - '0' + (num[i] - '0') * k;
41                 temp[i] = s % 10 + '0';
42                 temp[i - 1] = s / 10 + '0';
43             }
44             int s = (num[0] - '0') * k;
45             if (s / 10 != 0) {
46                 flag = false;
47                 break;
48             } else temp[0] = s + temp[0];
49             if (!compare()) {
50                 flag = false;
51                 break;
52             }
53         }
54         if (flag) cout << num << " is cyclic" << endl; 
55         else cout << num << " is not cyclic" << endl; 
56     }
57     return 0;
58 }