回文平方
找出1–300中,那些数字的平方转化为B进制后是一个回文数,输出该数字的B进制形式和其平方的B进制形式
输入样例:
10
输出样例:
1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696
思路:
1.进制转换:短除法。每次将待转化数字n%b,得到余数放到string类型res末尾,并将n/=b,直到n为0时短除法结束,将res翻转reverse(res.begin(), res.end())得到转化后的b进制。
while(n) res += get(n % b), n /= b; //模拟短除法
2.回文判断:双指针
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//获得短除法每次得到的余数(针对进制大于10的情况)
char get(int n)
{
return n <= 9? n + '0': n - 10 + 'A';
}
//数字n转化为b进制
string base(int n, int b)
{
string res;
while(n) res += get(n % b), n /= b; //模拟短除法
reverse(res.begin(), res.end());
return res;
}
//判断是否为回文数
bool check(string num)
{
for(int i = 0, j = num.size()-1; i < j; i++, j--)
{
if(num[i] != num[j]) return false;
}
return true;
}
int main()
{
int b;
cin >> b;
for(int i = 1; i <= 300; i++)
{
auto num = base(i*i, b);
if(check(num))
{
cout << base(i, b) << ' ' << num << endl;
}
}
return 0;
}