UVa 106 Fermat vs. Pythagoras

解題策略:

勾股定理 A²+B²=C²，或者叫做畢氏定理，符合公式的數對(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)，用以下公式代
A = X² - Y²
B = 2XY
C = X² + Y²
得出的A,B,C就是一組勾股數。

若 (X,Y) 恰好互質而且一奇一偶，那麼會得到一組(A,B,C)互質的勾股數。

知道通解後，雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。

找出不屬於勾股數的數字，直接開一個 size=1000000 的陣列來記錄所有出現過的數字 (用array或是bitset都成)。別忘了一點，我們上面只列出互質的勾股數，但是勾股數的任意整數倍也都是勾股數，如(3,4,5) (6,8,10) (9,12,15)，這些數字也都必須列入紀錄。

閒聊

我知道Fermat是費瑪，不過標題看很久才發現P先生是畢達哥拉斯orz，對於世界第一的先生(Runtime 0.008秒 by Java)，感到由衷的敬佩。