总时间限制: 1000ms 内存限制: 65536kB描述
若一个n位的数字串满足下述条件,则称其是循环数(cyclic):将这个数字串视为整数(可能带有前导0),并用任意一个 1 到 n 之间(包含1和n)的整数去乘它时, 会得到一个将原数字串首尾相接后,再在某处断开而得到的新数字串所对应的整数。例如,数字 142857 是循环数,因为: 142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142。
请写一个程序判断给定的数是否是循环数。
注意:在此题中,输入数字串允许带前导0,且前导0不能被忽略,例如“01”是两位数字串,而“1”是一位数字串。但将数字串转化为整数做乘法运算或比较运算时,可以忽略前导0。
输入一行,一个长度在 2 到 60 位之间的数字串。输出一个整数,若输入的数字串是循环数,输出1,否则输出0。样例输入
142857
样例输出
1
来源1047
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 char a[1001];
6 char ans[1001];
7 char p[80]={"016393442622950819672131147540983606557377049180327868852459"};
8 char z[80]={"0169491525423728813559322033898305084745762711864406779661"};
9 int main()
10 {
11 gets(a);
12 if(strcmp(a,p)==0||strcmp(a,z)==0)
13 {
14 cout<<1;
15 return 0;
16 }
17 int l=strlen(a);
18 for(int i=2;i<=6;i++)
19 {
20 memset(ans,0,sizeof(ans));
21 for(int j=0;j<l;j++)
22 {
23 char d[101];//临时储存now转换出来的结果
24 int now=(a[j]-48)*i;
25 if(now>=10)
26 {
27 int now2=1;
28 if(now/10+ans[j-1]>=58)
29 {
30 ans[j-2]=((((ans[j-1]-48)+(now/10)))/10)+ans[j-2];
31 ans[j-1]=(((ans[j-1]-48)+(now/10)))%10+48;
32 }
33 else ans[j-1]=now/10+ans[j-1];
34 now=now%10;
35 }
36 sprintf(d,"%d",now);
37 strcat(ans,d);
38 }
39 strncat(ans,ans,strlen(ans));
40 if(strstr(ans,a)!=NULL)
41 continue;
42 else
43 {
44 cout<<0;
45 return 0;
46 }
47 }
48 cout<<1;
49 return 0;
50 }