题目描述
回文数是指数字从前往后读和从后往前读都相同的数字。
例如数字 12321 就是典型的回文数字。
现在给定你一个整数 B,请你判断 1∼300 之间的所有整数中,有哪些整数的平方转化为 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
(暴力枚举) $O(300logb)$
- 10进制转b进制
- b进制再判断回文数
时间复杂度
main
函数循环300次,然后base
函数x / b。最多除$logb$次。因为相当于计算$b ^ k = x$, $k = logb$。
参考文献
C++ 代码
/*
1. 10进制转b进制
2. b进制再判断回文数
*/
#include <iostream>
#include <algorithm>
using namespace std;
int b;
char get(int x){
if (x <= 9) return x + '0';
return x - 10 + 'A';
}
string base(int x, int b){
string res;
while (x) res += get(x % b), x /= b;
reverse(res.begin(), res.end());
return res;
}
bool check(string num){
int i = 0, j = num.size() - 1;
while (i < j)
if (num[i] == num[j]) i ++, j --;
else return false;
return true;
}
int main(){
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;
}