2354. 八进制镜像坚果
1000ms
256MB
简单
字符串
题目描述
松鼠哈利需要挑选出一批魔力值在 $1 \sim N$ 之间的特殊坚果。这些坚果的魔力值（十进制正整数）必须同时满足以下两个要求：
1. 该数转换为**八进制**后是一个**回文数**（反向排列与原来一样的数，如八进制的 $11$、$121$ 等）。
2. 该数本身是一个**平方数**（可以写成某个整数的平方，如 $9 = 3^2$）。
请你帮助哈利从小到大输出所有满足要求的数。
输入格式
一行，输入一个十进制正整数 $N$ ($1 \le N \le 10^9$)。
输出格式
输出一行，包含若干个满足要求的十进制正整数，从小到大输出，正整数之间用一个空格隔开。
样例 1
输入 (Input)
20
输出 (Output)
1 4 9
样例说明
- **样例说明**：
在 $1 \sim 20$ 之间满足要求的数有：
- 1：转换为八进制为 1（回文数），且 $1 = 1^2$（平方数）。
- 4：转换为八进制为 4（回文数），且 $4 = 2^2$（平方数）。
- 9：转换为八进制为 11（回文数），且 $9 = 3^2$（平方数）。
因此输出 `1 4 9`。
- 对于所有数据：$1 \le N \le 10^9$。
- **算法提示与优化**：
由于 $N$ 的范围高达 $10^9$，如果从 1 到 $N$ 逐个遍历每个数字并判断，时间复杂度为 $O(N)$，必然会导致运行超时（TLE）。
我们可以**换个角度思考**：因为符合要求的数 $X$ 必须是平方数，我们可以直接枚举平方根 $i$。
- 令 $X = i^2$，由于 $X \le N$，所以 $i$ 的取值范围是 $1 \le i \le \sqrt{N}$。
- 当 $N = 10^9$ 时，$\sqrt{N} \approx 31622$，我们只需要循环最多 $31622$ 次。
- 在循环中，计算出 $X = i^2$，然后将其转换为八进制并判断是否为回文数即可。这样整体时间复杂度可以优化至 $O(\sqrt{N} \log_8 N)$，能在 1 毫秒内计算出结果。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功