a254: 畢氏‧三角‧製造
標籤 :
通過比率 : 100人/118人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-09-22 11:47

內容

        一個「最約畢氏三角」( primitive Pythagorean triangle) 的定義是指一個三角形滿足:三邊長a, b, c都是正整數且 a2 + b2 = c2 ,以及比較短的兩邊長a, b的最大公因數為1。老國王想要教導小王子學習畢氏三角的精隨與奧妙,於是給了小王子一些不同長度的木棍,要他利用這些木棍製造出許多「最約畢氏三角」。因為製造材料的關係,這些木棍僅被拿來用在比較短的兩個邊上,而且由於使用工具切木棍太危險了,因此木棍必須被整根使用。比方說妳有兩根長度分別是34的木棍,就可以做出一個三邊邊長分別是3, 4, 5的畢氏三角。

        現在小王子拿到了很多很多木棍,請你計算這些木棍最多可以製作多少個「最約畢氏三角」,注意每根木棍至多只能被用一次。

輸入說明

        每個測資檔內含有多組測資。每組測資第一列有一個正整數N(1<=N<=200),接下來包含了N個正整數代表木棍長度,所有數字都介於1999999之間。

輸出說明

        對於每一組測試資料請輸出能拿來湊出的最多最約畢氏三角的數量。

範例輸入
9
3 4 4 3 11 5 12 9 4
4
20 21 3021 220
5
28 195 1035 21412 37995
範例輸出
3
2
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1M
提示 :
標籤:
出處:
2011成功高中校內賽初賽第四題 [管理者:
david942j (文旋)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」