完全平方数

题目描述:

一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，求该数是多少？

输入格式:

无

输出格式:

输出从小到大的所有可能的若干数，一个数一行。

样例输入:

(双击复制)

无

样例输出:

(双击复制)

无

提示:

假设该数是x，加上100后的完全平方数用n²表示，再加168的完全平方数是m²表示。

那么由题意可知：n² = x + 100， m² = x + 100 + 168。

可得： m² - n² = (m+n) *( m-n) = 168。

 

解题思路
题目要求：找到一个数 x，满足：

x + 100 = m²

x + 268 = n² （因为加上100后再加168，总共加268）

推导过程
从两个等式可得：

n² - m² = 168

因式分解：(n + m)(n - m) = 168

确定枚举范围
设 n > m > 0，那么：

令 a = n + m

令 b = n - m
则 a × b = 168，且 a > b > 0，a 和 b 同奇偶（因为 n = (a+b)/2 必须是整数）

找 m 的范围
从 n = (a+b)/2 和 m = (a-b)/2 可得：

当 a 和 b 差距最小时，m 最大

168 的因数对中，最接近的两个数是 14 和 12

此时 m = (14-12)/2 = 1，n = (14+12)/2 = 13

当 a 和 b 差距最大时：

最大 a 是 168，最小 b 是 1（但 168 和 1 不同奇偶，不行）

实际可取的最大 a 是 84，对应 b = 2

此时 m = (84-2)/2 = 41，n = (84+2)/2 = 43

结论
因此：

m 最大为 41（当 a=84, b=2 时）

n 最大为 43（当 a=84, b=2 时）

所以代码中：

外层循环 m 从 1 到 43

内层循环 n 从 1 到 41
然后检查 (m+n)*(m-n) == 168 这个条件

当找到符合条件的 m 和 n 后，通过 m² - 100 得到原数 x（ x+100 = m²，所以 x = m² - 100)

时间限制: 1000ms
空间限制: 256MB

---

来源: 高中教材