题解：B4276 [蓝桥杯青少年组国赛 2023] 八进制回文平方数

xf20280111 · 2025-04-04 09:06:44 · 题解

思路

直接枚举 i 的值，时间复杂度 \mathcal{O}(n)。

显然过不了。

枚举 1 到 \sqrt{n}，再将他们平方之后转化成 8 进制后是不是回文数。

枚举回文数只需要转化进制时存入一个数组，然后判断是否对称即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
int a[N];
bool jz(int n){
    int i = 0;
    while(n != 0){
        a[i ++] = n % 8;
        n /= 8;
    }//转换进制
    for (int j = 0;j < i / 2;j++){
        if (a[j] != a[i - j - 1]) return false;
    }//判断回文
    return true;
}
int main()
{
    int n;cin >> n;
    for (int i = 1;i * i/*写成 sqrt(n) 精度容易出问题*/ <= n;i++){
        int x = i * i;
        if (jz(x)) {
            cout << x << " ";
        }
    }
    return 0;
}