AcWing 1346. 回文平方
原题链接
简单
作者:
feifei
,
2021-01-13 13:58:06
,
所有人可见
,
阅读 301
#include<iostream>
#include<stdio.h>
using namespace std;
int a[301], s[301][30], cnt[300];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= 300; i ++)a[i] = i * i;
for(int i = 1; i <= 300; i++)
{
//转换为n进制
int y = a[i], j = -1;
while(y)
{
s[i - 1][++ j] = y % n;
y = y / n;
}
cnt[i] = j;
}
for(int i = 1; i <= 300; i++)
{
for(int j = cnt[i], k = 0; j >= 0; j--, k++)
{
//如果该数字是回文,输出
if(s[i - 1][j] == s[i - 1][k] && k == cnt[i] / 2)
{
//将满足平方值转化为 n 进制后是回文数字那个数转换为n进制
//也就是输出的前一个数字转换为n进制
int y = i, l = -1, tmp[30];
while(y)
{
tmp[++ l] = y % n;
y = y / n;
}
//输出前一个n进制数字
for(int u = l;u >= 0; u--)
{
if(tmp[u] >= 10)printf("%c", tmp[u] + 55);
else cout << tmp[u];
}
cout << " ";
//输出后一个n进制数字
for(int c = cnt[i]; c >= 0 ; c--)
{
if(s[i - 1][c] >= 10)printf("%c", s[i - 1][c] + 55);
else cout << s[i - 1][c];
}
cout << endl;
break;
}
else if(s[i - 1][j] != s[i - 1][k])break;
}
}
return 0;
}