1000ms

Difficulty: 4

所属公司 : 网易

时间 :2025年10月9日

算法与标签>构造

会员或题库专享

请先，开通会员或购买题库网易题库，可解锁完整内容。

购买网易题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（网易题库），可解锁完整内容。

购买题库开通会员

解题思路

核心定义：一个正整数既是回文数，又是某个回文数的平方，称为“超级回文数”。
直接在区间内逐个检查代价巨大。由于 $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）。

题目内容

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

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