首页 > 代码库 > 洛谷P1206 [USACO1.2]回文平方数 Palindromic Squares
洛谷P1206 [USACO1.2]回文平方数 Palindromic Squares
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 = 300;int b,a[maxn];void zhuanhuan(int x){ int a1[maxn]; int i = 0; while (x > 0) { a1[++i] = x % b; x /= b; } while (i) { if (a1[i] < 10) printf("%d", a1[i]); else printf("%c", a1[i] - 10 + ‘A‘); i--; }}void huiwen(int x1){ int temp = 0; int x = x1 * x1; while (x > 0) { a[++temp] = x % b; x /= b; } int t = temp, i = temp; while (i > 0 && a[i] == a[t - i + 1]) i--; if (i == 0) { zhuanhuan(x1); printf(" "); while (temp) { if (a[temp] < 10) printf("%d", a[temp]); else printf("%c", a[temp] - 10 + ‘A‘); temp--; } printf("\n"); }}int main(){ scanf("%d", &b); for (int i = 1; i <= maxn; i++) huiwen(i); return 0;}
洛谷P1206 [USACO1.2]回文平方数 Palindromic Squares