链接：[http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1207]
问题描述是：给定一个大于0的整数N(1<=N<=10^8),判断其是否可能是一个直角三角形的直角边(这个三角形的三条边必须都是整数)…
这个题还是做得我挺郁闷的。。。刚开始完全没思路。。。后面没办法，硬着头皮往下想。
对于勾股定理a^2 + b^2 = c^2，假设N是a,可以得到a^2 = (c + b) * (c -b), 那么(c + b)和(c - b)是a^2的2个因子,而且(c+b)>=a,(c-b)<=a。。。
到这一步已经可以用程序轻松解决出来了,但是对于任意一个整数N来说,其复杂度都是O(N),那么计算量还是很大的…
这个时候只需要枚举1-N,求出a^2的2个因子,然后求c和b,如果能得出c和b都是正整数那么,就满足条件了…
但是这样还是过不了题,因为数据量不会这么小…数据量好像有10000组。。。
那么还需要推导出进一步的结论…
因为1和a^2一定是a^2的一对因子,那么(c+b) = a^2和(c-b) = 1一定可以成功,
则可以推导出，2 c = a^2 + 1。
要c可解,a必须为奇数,那么可以推导出如果a是奇数,一定是直角边了。。。
如果a是偶数了,可以化简为 4 (a / 2) ^ 2 = 4 （c + b) \ (c - b) = (2c + 2b) * (2c - 2b) = a ^ 2，那么继续推导也可以得到一样的结果了…
结论就是:对于大于等于3的正整数都可以是一条直角边(>=3也可以根据上面的c和b是正整数推导出来)…