Problem J32: Automorphic Numbers / 自守数

版权信息： JLOJ2451

任务总览

题目描述

自守数 是指一个数的平方的 末尾部分等于它本身 的自然数。

例如：

• $5 ^ 2 = 25$，尾数是 25 的最后一位是 5，符合；
• $76 ^ 2 = 5776$，尾数为 76，等于原数 76，符合。

请你输出指定范围内所有的自守数。

输入格式

输入一行两个正整数 $m$ 和 $n$（$1 \leq m < n \leq 10 ^ 9$），表示待检查的区间范围。

输出格式

将区间 $[m, n]$ 内的所有自守数​ 逐行输出 ​，每个数占一行，按从小到大顺序排列。

输入输出样例

输入示例

1 200000

输出示例

1
5
6
25
76
376
625
9376
90625
109376

题目分析与解法

✅ 定义回顾：

若某个正整数 $x$ 满足：

$x ^ 2 \bmod 10 ^ k = x$其中 $k$ 是 $x$ 的位数，则 $x$ 是​ 自守数 ​。

✅ 解法建议（暴力判断）：

1. 遍历 $x$ 从 $m$ 到 $n$；
2. 令 $k = \text{ len }(x)$，即 $x$ 的十进制位数；
3. 判断： $x ^ 2 \bmod 10 ^ k = x4$.满足条件则输出。

时间复杂度分析

若范围较大建议只枚举固定自守数（数量稀少），或使用打表优化。