2011年3月21日 星期一

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),用以下公式代
A = X2 - Y2
B = 2XY
C = X2 + Y2
得出的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),感到由衷的敬佩。

6 則留言:

  1. hello,台湾同胞你好,UVA刷了多少题了?

    回覆刪除
  2. 這題有個蠻 tricky 的地方 , 就是您程式碼的 index 部分用的是1000

    // 用雙層迴圈跑遍(x,y)所有可能的值
    for (int x=1; x<1000; ++x){

    如果傻傻的用最大值 1000000 代入 , 還是會超過時間QQ

    回覆刪除
  3. 請問 再快 就只能建表了嗎?

    回覆刪除
    回覆
    1. 其實我不知道該怎麼更快,你可以試試看建表,不知道建表能不能達到0.008秒XD

      刪除
    2. http://zerojudge.tw/ShowProblem?problemid=a247
      被測資打敗了...

      刪除
    3. 原來現在ZJ也有這題了,今天晚上來挑戰一下XD

      刪除