自守数是指一个数的平方的尾数等于该数自身的自然数。
例如：
$25^2=625$
$76^2=5776$
$9376^2=87909376$
请求出所有的自守数$n$, $0 \le n \le 200000$
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $578$ | 正确数量 | $369$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 字符串 |
自守数是指一个数的平方的尾数等于该数自身的自然数。
例如：
$25^2=625$
$76^2=5776$
$9376^2=87909376$
请求出所有的自守数$n$, $0 \le n \le 200000$
$200000$以内的自守数(包括0, 每个数末尾输出两个空格)
0 1 5 6 25 ....
若采用“求出一个数的平方后再截取最后相应位数”的方法显然是不可取的，因为计算机无法表示过大的整数。
分析手工方式下整数平方(乘法)的计算过程，以376为例：
376 被乘数
X 376 乘数
----------
2256 第一个部分积=被乘数*乘数的倒数第一位
2632 第二个部分积=被乘数*乘数的倒数第二位
1128 第三个部分积=被乘数*乘数的倒数第三位
----------
141376 积
本问题所关心的是积的最后三位。分析产生积的后三位的过程，可以看出，在每一次的部分积中，并不是它的每一位都会对积的后三位产生影响。总结规律可以得到：在三位数乘法中，对积的后三位产生影响的部分积分别为：
第一个部分积中：被乘数最后三位*乘数的倒数第一位
第二个部分积中：被乘数最后二位*乘数的倒数第二位
第三个部分积中：被乘数最后一位*乘数的倒数第三位
将以上的部分积的后三位求和后截取后三位就是三位数乘积的后三位。这样的规律可以推广到同样问题的不同位数乘积。
按照手工计算的过程可以设计算法编写程序。
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$0 $ms] | WaFer | 840809 | 2022-04-13 09:55:55 |
| 内存最少[$0 $KB] | 只能过个样例~~~ | 576236 | 2020-04-03 11:48:31 |
| 第一AC | 刘观圣@网络工程142 | 2040 | 2016-05-15 16:44:12 |
| 第一挑战 | 刘观圣@网络工程142 | 2040 | 2016-05-15 16:44:12 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|---|---|---|
| 1376 | NOIP2019暑期集训-第一单元：枚举、模拟 | 2019-08-04 08:00:00 | 请登录 |