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

· · 题解

题目简述

给定一个数 N，判断不超过 N 的数中有几个数满足：

  1. 为完全平方数
  2. 转为八进制下为一个回文数

主要思路

考虑枚举。可以直接枚举 N 以内的完全平方数，然后判断八进制下是否为一个回文数即可。

对于十进制数转八进制数，可以使用短除法：使答案与这个数取模 8 的结果拼接，再让这个数除以 8，直到这个数为 0，最后翻转过来即可。

AC Code

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double db;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
inline ll _abs(ll a) { if (a < 0) return -a; return a; }
inline ll _pow(ll a, ll b) { ll x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
// ----------------------------

// ----------------------------

// ----------------------------
string to_base8(int x) {  // 转八进制函数
    string res = "";
    while (x) {
        res += char(x % 8 + '0');
        x /= 8;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n; cin >> n;
    // ----------------------------
    string s1, s2;
    int x = 1;
    while (x * x <= n) {
        s1 = to_base8(x * x);
        // 翻转字符串判断是否为回文数
        s2 = s1; reverse(s2.begin(), s2.end());
        if (s1 == s2) cout << x * x << ' ';
        x++;
    }
    return 0;
}