P1206 [USACO1.2]回文平方数 Palindromic Squares
- 271通过
- 501提交
- 题目提供者该用户不存在
- 标签USACO
- 难度普及-
提交 讨论 题解
最新讨论
- 暂时没有讨论
题目描述
回文数是指从左向右念和从右向左念都一样的数。如12321就是一个典型的回文数。
给定一个进制B(2<=B<=20,由十进制表示)，输出所有的大于等于1小于等于300（十进制下）且它的平方用B进制表示时是回文数的数。用’A’,’B’……表示10，11等等
输入输出格式
输入格式：
共一行，一个单独的整数B(B用十进制表示)。
输出格式：
每行两个B进制的符合要求的数字，第二个数是第一个数的平方，且第二个数是回文数。
输入输出样例
输入样例#1：
10
输出样例#1：
1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696
说明
题目翻译来自NOCOW。
USACO Training Section 1.2
分析：看到1到300的平方就应该知道本题要枚举，那么枚举1到300的平方转换到B进制然后检验是否是回文数即可，关键是怎么转换进制呢？
如果10进制的数转换为n进制的数，那么就把这个数不断除以n,保留余数，除到商为0为止，那么把余数反过来就是结果了，举个例子：
3 / 2 = 1 ...... 1
1 / 2 = 0 ...... 1
那么答案就是11,如果是n进制数转换为10进制呢？那么从这个数的最右边一位开始乘n^(i-1),i是从右边起的第几位,最后加起来，举个例子：二进制11转换成10进制：
1 * 2^(1 - 1) + 1 * 2 ^ (2 - 1) = 3
原理就是数的表示：123可以表示为1*10^2 + 2 * 10 ^ 1 + 3 * 10 ^ 0.然后注意一下当数大于9的时候需要用字母表示即可.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int maxn = ; int b,a[maxn]; void zhuanhuan(int x)
{
int a1[maxn];
int i = ;
while (x > )
{
a1[++i] = x % b;
x /= b;
}
while (i)
{
if (a1[i] < )
printf("%d", a1[i]);
else
printf("%c", a1[i] - + 'A');
i--;
}
} void huiwen(int x1)
{
int temp = ;
int x = x1 * x1;
while (x > )
{
a[++temp] = x % b;
x /= b;
}
int t = temp, i = temp;
while (i > && a[i] == a[t - i + ])
i--;
if (i == )
{
zhuanhuan(x1);
printf(" ");
while (temp)
{
if (a[temp] < )
printf("%d", a[temp]);
else
printf("%c", a[temp] - + 'A');
temp--;
}
printf("\n");
}
} int main()
{
scanf("%d", &b);
for (int i = ; i <= maxn; i++)
huiwen(i); return ;
}