UVa 106 Fermat vs. Pythagoras
解題策略:
勾股定理 A2+B2=C2,或者叫做畢氏定理,符合公式的數對(A,B,C)就叫一組勾股數 (畢氏三元數)。題目給一個正整數N,要我們找出兩個答案,第一: 0~N之間總共有幾組互質勾股數? 第二: 0~N之間有幾個數完全不屬於任何一組勾股數? 我舉個例子N=10,那麼0~10之間可以找到兩組勾股數(3,4,5)與(6,8,10),其中只有(3,4,5)一組互質,所以第一個答案是1。再來,3,4,5,6,8,10 都屬於某一組勾股數,完全沒用到的數字是1,2,7,9,共四個數,所以第二個答案是4。
解題關鍵在於如何快速找出一堆勾股數。我想就別折騰了,要解這題就要知道勾股數的通解,單純用暴力搜尋鐵定超時。
從維基百科的勾股數條目參考來的通解:
給一個任意數對(X,Y),用以下公式代知道通解後,雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。
A = X2 - Y2
B = 2XY
C = X2 + Y2
得出的A,B,C就是一組勾股數。
若 (X,Y) 恰好互質而且一奇一偶,那麼會得到一組(A,B,C)互質的勾股數。
找出不屬於勾股數的數字,直接開一個 size=1000000 的陣列來記錄所有出現過的數字 (用array或是bitset都成)。別忘了一點,我們上面只列出互質的勾股數,但是勾股數的任意整數倍也都是勾股數,如(3,4,5) (6,8,10) (9,12,15),這些數字也都必須列入紀錄。
hello,台湾同胞你好,UVA刷了多少题了?
回覆刪除這題有個蠻 tricky 的地方 , 就是您程式碼的 index 部分用的是1000
回覆刪除// 用雙層迴圈跑遍(x,y)所有可能的值
for (int x=1; x<1000; ++x){
如果傻傻的用最大值 1000000 代入 , 還是會超過時間QQ
請問 再快 就只能建表了嗎?
回覆刪除其實我不知道該怎麼更快,你可以試試看建表,不知道建表能不能達到0.008秒XD
刪除http://zerojudge.tw/ShowProblem?problemid=a247
刪除被測資打敗了...
原來現在ZJ也有這題了,今天晚上來挑戰一下XD
刪除