【USACO 1.2.4】回文平方数

【题目描述】

回文数是指从左向右念和从右向左念都一样的数。如12321就是一个典型的回文数。

给定一个进制B(2<=B<=20,由十进制表示)，输出所有的大于等于1小于等于300（十进制下）且它的平方用B进制表示时是回文数的数。用’A’,’B’……表示10，11等等。

【格式】

INPUT FORMAT:

file (palsquare.in)

共一行，一个单独的整数B(B用十进制表示)。

OUTPUT FORMAT:

file (palsquare.out)

每行两个B进制的符合要求的数字，第二个数是第一个数的平方，且第二个数是回文数。

【分析】

枚举+进制转换。

 1 #include <cstdlib>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 const int maxl=1000;
 7 using namespace std;
 8 int shu_1[maxl],shu_2[maxl];
 9 int temp[maxl];
10 //进制转换 
11 void change(int *shu,int num,int system);
12 void print(int *shu);
13 bool check(int *shu);//检查是否是回文数 
14 int main()
15 {
16     int n,i;
17     
18     //文件操作
19     freopen("palsquare.in","r",stdin);
20     freopen("palsquare.out","w",stdout);
21     scanf("%d",&n);
22     
23     for (i=1;i<=300;i++)
24     {
25         change(shu_1,i,n);
26         change(shu_2,i*i,n);
27         if (check(shu_2))
28         {
29             print(shu_1);printf(" ");
30             print(shu_2);printf("
");
31         }
32     } 
33     return 0;
34 }
35 //把一个num转换成system进制的数 
36 void change(int *shu,int num,int system)
37 {
38      int point=0;
39      memset(shu,0,sizeof(shu));
40      memset(temp,0,sizeof(temp));
41      point++;
42      //进制转换 
43      while (num!=0)
44      {
45            int t;
46            t=num%system;
47            num=num/system;
48            temp[point++]=t;
49      }
50      point--;
51      for (int i=point;i>=1;i--) shu[point-i+1]=temp[i];
52      shu[0]=point;//长度 
53      return;
54 }
55 bool check(int *shu)
56 {
57      int point=shu[0],i;
58      for (i=1;i<=(point/2)+1;i++)
59      if (shu[i]!=shu[point-i+1]) return 0;
60      return 1;
61 }
62 void print(int *shu)
63 {
64      for (int i=1;i<=shu[0];i++)
65      {
66          if (shu[i]>=10) printf("%c",char(shu[i]-10+'A'));
67          else printf("%d",shu[i]);
68      }
69 }