解题思路

核心定义：一个正整数既是回文数，又是某个回文数的平方，称为“超级回文数”。
直接在区间内逐个检查代价巨大。由于 $R\le 10^{20}$ ，其平方根上界为 $10^{10}$ 。因此我们只需生成所有不超过 $10^{10}$ 的回文根，再对每个根平方并判断是否回文且落在 $[L,R]$ 内。
生成回文根的方法（经典构造）
- 设“半串”为从 $1$ 到 $99999$ 的十进制数串 s（长度最多 5）。
- 奇数长度回文根：s + reverse(s[:-1])（如 123→12321）。
- 偶数长度回文根：s + reverse(s)（如 123→123321）。

P3856.第1题-超级回文数

1000ms

Difficulty: 4

所属公司 : 网易

算法与标签>构造

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。

现在，给定两个正整数 $L$ 和 $R$ ，请按照从小到大的顺序打印包含在范围 $[L,R]$ 中的所有超级回文数。

注： $R$ 包含的数字不超过 $20$ 位

回文数定义：将该数各个位置的数字反转排列，得到的数和原数一样，例如 $676,2332,10201$ 。

输入格式： $L,R$ 。例如 $4,1000$

正整数 $L$ 和 $R$

从小到大的顺序打印包含在范围 $[L,R]$ 中的所有超级回文数

输入

4,1000

输出

[4,9,121,484]

说明

将 $List<Long>$ 数组直接打印出来即可满足格式要求

输入

预期输出（选填）