【每日一题5】AcWing 1346. 回文平方

Day5 AcWing 1346. 回文平方

思路

1. 十进制转化成其他进制：短除法
2. 其他进制转化成十进制：秦九韶算法
3. 其他进制转化成其他进制
   （1）十进制过渡
   （2）短除法

拓展

1. AcWing 124. 数的进制转换

代码

#include <bits/stdc++.h>
using namespace std;

char get(int x)
{
    if(x<=9) return x+'0';
    return x-10+'A';
}
string base(int n,int b)
{
    string num;
    while(n)num+=get(n%b),n/=b;
    reverse(num.begin(),num.end());
    return num;
}

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;
}