自动搬运

查看原文

来自洛谷，原作者为

	FJ_EYoungOneC 这个人很勤快，但是他并不想留下什么

搬运于2025-08-24 21:18:17，当前版本为作者最后更新于2025-04-04 12:14:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

考虑暴力，枚举 $1 \sim n$，判断每个数是否合法，复杂度 $O(n\log n)$。

考虑优化，我们可以尝试枚举所有的平方数，再判断转换为八进制后是否一个回文数，时间复杂度 $O(\sqrt n\log \sqrt n)$。

AC_Code

#include <iostream>
#include <algorithm>

using namespace std;

int n;

bool is_pali(string str)
{
    string rts = str;
    reverse(rts.begin(), rts.end());
    return rts == str;
}

string get(int x)
{
    string res;
    while (x)
        res += x % 8 + '0', x /= 8;
    return res;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n / i; ++ i )
        if (is_pali(get(i * i)))
            cout << i * i << ' ';
    
    return 0;
}