[USACO1.2] 回文平方数 Palindromic Squares

题目描述

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

给定一个用十进制表示的正整数 $B$，输出所有 $[1,300]$ 中，它的平方用 $B$ 进制表示时是回文数的数。

输入格式

共一行，一个单独的正整数 $B$。

输出格式

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

注意大于 $9$ 的数，用字母表示。如用 A 表示 $10$，B 表示 $11$，用第 $n$ 个大写字母表示 $n+9$。

样例 #1

样例输入 #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

提示

【数据范围】
对于 $100\%$ 的数据，$2 \le B \le 20$

题目翻译来自NOCOW。

USACO Training Section 1.2

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a[1001],lena,lenb,b[1001],p,B,k,j,c[1001];
	bool ok;
	cin>>B;
	for(int i=1;i<=300;i++)
	{
		p=i;
		lena=0;
		while(p>0)
		{
			lena++;
			c[lena]=p%B;
			p/=B;
		}
		p=pow(i,2);
		lenb=0;
		while(p>0)
		{
			lenb++;
			c[lenb]=p%B;
			p/=B;
		}
		k=1;
		while(k<=lenb)
		{
			b[k]=a[k];
			k++;
		}
		ok=true;
		k=1;j=lenb;
		while(k<=lenb&&j>=1)
		{
			if(a[k]!=b[j]) ok=false; 
			k++;j--;
		}
		if(ok)
		{
			for(k=1;k<=lena;k++)
			{
				if(c[k]<10) cout<<c[k];
				else cout<<char('A'+c[k]-10);
			}
			cout<<" ";
			for(k=1;k<=lenb;k++)
			{
				if(a[k]<10) cout<<a[k];
				else cout<<char('A'+a[k]-10);
			}
			cout<<endl;
		}
	}
	return 0;
}