回文平方

回文数是指数字从前往后读和从后往前读都相同的数字。

例如数字 12321 12321 12321 就是典型的回文数字。

现在给定你一个整数 B B B，请你判断 1 ∼ 300 1∼300 1∼300 之间的所有整数中，有哪些整数的平方转化为 B B B 进制后，其 B B B 进制表示是回文数字。

输入格式
一个整数 B B B。

输出格式
每行包含两个在 B B B 进制下表示的数字。

第一个表示满足平方值转化为 B B B 进制后是回文数字那个数，第二个数表示第一个数的平方。

所有满足条件的数字按从小到大顺序依次输出。

数据范围
2 ≤ B ≤ 20 , 2≤B≤20, 2≤B≤20,
对于大于 9 9 9 的数字，用 A A A 表示 10 10 10，用 B B B 表示 11 11 11，以此类推。

输入样例：

10 10 10

输出样例：

1 1 1 1 1 1
2 2 2 4 4 4
3 3 3 9 9 9
11 11 11 121 121 121
22 22 22 484 484 484
26 26 26 676 676 676
101 101 101 10201 10201 10201
111 111 111 12321 12321 12321
121 121 121 14641 14641 14641
202 202 202 40804 40804 40804
212 212 212 44944 44944 44944
264 264 264 69696 69696 69696

分析：
常规方法：枚举，核心是如何把数字转为 B B B进制。一般用短除法来实现进制转换，只需要每次除一下进制数，写下来余数，然后倒着把余数写出来就是转换之后的数了，这里恰好能利用 s t r i n g string string变量的加法运算来简便的实现这个功能，这样就不用额外开一个数组每次累加此数组 ∗ 10 *10 ∗10了。
但是要注意题目中 B B B可能大于 10 10 10，所以还需要考虑 10 ∼ A ， 11 ∼ B . . . 10\sim A，11\sim B... 10∼A，11∼B...的问题，正好可以一并用 s t r i n g string string类型解决。

代码：

#include<bits/stdc++.h>
using namespace std;
char get(int x){
    if(x<=9) return x+'0';
    else return x+'A'-10;
}
string base(int x,int b){
    string num;
    while(x) num+=get(x%b),x/=b;
    reverse(num.begin(),num.end());//由于逆序存的，所以需要逆回来
    return num;
}
bool check(string num){
    int i;
    for(i=0;i<num.size();i++){
        if(num[i]!=num[num.size()-i-1]) return 0;
    }
    return 1;
}
int main(){
    int b,i;
    cin>>b;
    for(i=1;i<=300;i++){
        auto num=base(i*i,b);
        if(check(num)) cout<<base(i,b)<<" "<<num<<endl;
    }
}

拓展：如何将一个 B B B进制数转为十进制数？秦九韶算法。

把一个n次多项式

改写成如下形式：
把 一 个 n 次 多 项 式 f ( x ) = a n x n + a n − 1 x n − 1 + . . . + a 1 x + a 0 把一个n次多项式f(x)=a_{n}x^n+a_{n-1}x^{n-1}+...+a_1x+a_0 把一个n次多项式f(x)=an​xn+an−1​xn−1+...+a1​x+a0​
改 写 成 ： f ( x ) = ( . . . ( ( a n x + a n − 1 ) x + a n − 2 ) x + . . . + a 1 ) x + a 0 改写成：f(x)=(...((a_{n}x+a_{n-1})x+a_{n-2})x+...+a_1)x+a_0 改写成：f(x)=(...((an​x+an−1​)x+an−2​)x+...+a1​)x+a0​
这样只需要计算 n n n次乘法和 n n n次加法。