本文最后更新于 2018 年 5 月 10 日，其中的内容可能有所发展或发生改变，敬请注意。
1.平方末尾
时长限制: X MS 内存限制: X KB
描述
能够表示为某个整数的平方的数字称为“平方数”
比如，25,64
虽然无法立即说出某个数是平方数，但经常可以断定某个数不是平方数。
因为平方数的末位只可能是：[0, 1, 4, 5, 6, 9] 这6个数字中的某个。
所以，4325435332必然不是平方数。
如果给你一个2位或2位以上的数字，你能根据末位的两位来断定它不是平方数吗？
请计算一下，一个2位以上的平方数的最后两位有多少种可能性？
输入
无输入
输出
一个整数，表示2位以上的平方数最后两位的不同情况数。
不要填写任何多余内容（比如，说明解释文字等）
解题思路
本题实现方式多样，总的来说其实就是记录不同的数作为末尾出现了种。
我们可以用hashMap，也可以纯粹的用一个布尔类型数组记录。
并且由于 100 × n (n为任意非负整数)的末尾两位必定为0
且 n × n (n>=100) 可以拆分为
(n % 100) * n + (n - n % 100) * n，
因为我们只关注最后两位所以加号后的部分后两位一定为0所以直接无视
得到 (n % 100) * n
同样拆分可以得到
n × n (n>=100) 结果的后两位与 (n % 100) * (n % 100) 的结果后两位相同
所以我们只需要计算 0~99 的平方结果后两位有多少种即可
实现并得到以下源码
个人思路实现源码(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public class Main { public static void main(String[] args) { boolean[] numArr = new boolean[100]; for (int i = 0; i < 100; i++) { numArr[(i * i) % 100] = true; } int sum = 0; for (int i = 0; i < 100; i++) { if (numArr[i]) sum++; } System.out.println(sum); } } //输出结果为 22 |
