题目描述

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

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

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

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<string>
#include<algorithm>                     //reverse
using namespace std;
char get(int n)                         // 10->A
{
    if(n<10)
        return n + '0';
    else
        return n - 10 + 'A';
}
string change(int x,int y)              //进制转换
{
    string num;
    while(x)
    {
        num += get(x%y);
        x = x/y;
    } 
    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 = change(i*i,b);
        if(check(num))
            cout<<change(i,b)<<" "<<change(i*i,b)<<endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla