问题 1035 --自守数问题

1035: 自守数问题

"
时间限制 $1$ 秒/Second(s) 内存限制 $128$ 兆字节/Megabyte(s)
提交总数 $361$ 正确数量 $321$
裁判形式 特别裁判/Special 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 积

本问题所关心的是积的最后三位。分析产生积的后三位的过程,可以看出,在每一次的部分积中,并不是它的每一位都会对积的后三位产生影响。总结规律可以得到:在三位数乘法中,对积的后三位产生影响的部分积分别为:

第一个部分积中:被乘数最后三位*乘数的倒数第一位

第二个部分积中:被乘数最后二位*乘数的倒数第二位

第三个部分积中:被乘数最后一位*乘数的倒数第三位

将以上的部分积的后三位求和后截取后三位就是三位数乘积的后三位。这样的规律可以推广到同样问题的不同位数乘积。

按照手工计算的过程可以设计算法编写程序。

推荐代码 查看1035 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 断水流大师兄 489306 2019-10-12 21:19:50
内存最少[$0 $KB] 断水流大师兄 489306 2019-10-12 21:19:50
第一AC 刘观圣@网络工程142 2040 2016-05-15 16:44:12
第一挑战 刘观圣@网络工程142 2040 2016-05-15 16:44:12

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1376 NOIP2019暑期集训-第一单元:枚举、模拟 2019-08-04 08:00:00 请登录