鏈接：
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1207
問(wèn)題描述是：給定一個(gè)大于0的整數(shù)
N(1<=N<=10^8),判斷其是否可能是一個(gè)直角三角形的直角邊(這個(gè)三角形的三條邊必須都是整數(shù))...
這個(gè)題還是做得我挺郁悶的。。。剛開始完全沒(méi)思路。。。后面沒(méi)辦法，硬著頭皮往下想，對(duì)于勾股定理a^2 + b^2 = c^2,假設(shè)N是a,
可以得到a^2 = (c + b) * (c -b), 那么(c+b)和(c-b)是a^2的2個(gè)因子,而且(c+b)>=a,(c-b)<=a。。。
到這一步已經(jīng)可以用程序輕松解決出來(lái)了,但是對(duì)于任意一個(gè)整數(shù)N來(lái)說(shuō),其復(fù)雜度都是O(N),那么計(jì)算量還是很大的...
這個(gè)時(shí)候只需要枚舉1-N,求出a^2的2個(gè)因子,然后求c和b,如果能得出c和b都是正整數(shù)那么,就滿足條件了...
但是這樣還是過(guò)不了題,因?yàn)閿?shù)據(jù)量不會(huì)這么小...數(shù)據(jù)量好像有
10000組。。。
那么還需要推導(dǎo)出進(jìn)一步的結(jié)論...
因?yàn)?和a^2一定是a^2的一對(duì)因子,那么(c+b) = a^2和(c-b) = 1一定可以成功,
則可以推導(dǎo)出,2*c = a^2 + 1;
要c可解,a必須為奇數(shù),那么可以推導(dǎo)出如果a是奇數(shù),一定是直角邊了。。。
如果a是偶數(shù)了,可以化簡(jiǎn)為4*(a/2)^2 = 4*（c+b)*(c-b) = (2c+2b)*(2c-2b) = a^2,那么繼續(xù)推導(dǎo)也可以得到一樣的結(jié)果了...
結(jié)論就是:對(duì)于大于等于3的正整數(shù)都可以是一條直角邊(>=3也可以根據(jù)上面的c和b是正整數(shù)推導(dǎo)出來(lái))...