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

· · 题解

思路

60 分

我们可以写一个函数 check，判断这个数的八进制是否回文且这个数是否是平方数。但不难发现：10^9 的数据显然是抗不下来的，一定会 TLE。

正解（100 分）

由于我们需要缩小时间复杂度，因此我们可以直接在 for 循环里就设成 i \times i 了，就直接去判断每个平方数的八进制是否回文，减少了许多不必要的损失。

代码

#include <bits/stdc++.h>
using namespace std;
inline bool check(int x){
    bool f=0;
    vector<int> v;
    while(x){
        v.push_back(x%8);
        x/=8;
    }
    string s="";
    for(int i=v.size()-1;i>=0;i--){
        s.push_back(v[i]+'0');
    }
    string res=s;
    reverse(res.begin(),res.end());
    f=(res==s);
    return f;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(NULL);
    int N;
    cin>>N;
    for(int i=1;i*i<=N;i++){
        if(check(i*i)){
            cout<<i*i<<' '; 
        }
    }
    return 0;
}