主題

ZeroJudge - a254: 畢氏‧三角‧製造 解題心得

Not In My Back Yard | 2020-11-03 00:00:01

題目連結:


題目大意:
輸入有多筆測試資料,每筆佔兩列。測資第一列給定一正整數 N (1 ≦ N ≦ 200),代表有 N 根木棍。接著的第二列給定 N 個正整數(皆介於 1 ~ 9999999 之間),代表這 N 根木棍的長度。

試問這 N 根木棍的長度中最多可以湊出多少對的 (a, b) ,使得 a ^ 2 + b ^ 2 為一個完全平方數且 a 與 b 的最大公因數為 1。



範例輸入:
9
3 4 4 3 11 5 12 9 4
4
20 21 3021 220
5
28 195 1035 21412 37995


範例輸出:
3
2
2


解題思維:
因為對於 a ^ 2 + b ^ 2 = c ^ 2  中的每個正整數 a 值,只會存在一個與之相對的正整數 b 滿足該式且 c 為一正整數。

因此,我們只要對於每根木棍去與其他木棍配對看看。如果木棍 a 可以與木棍 b 滿足上式,則將這兩根木棍設為「已使用過」,並將配對的計數 + 1。

最後看配對數多少即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
69 巴幣: 0
胖胖貓
雖然這題我也是直接貪婪法去做,但事後想了一下好像不太對...。
我想問一下根據最約畢氏定理的 b 對應 a 是一對一的嘛?( 我沒找到相關證明 )
貪婪法:枚舉目前沒選到且最短邊長,選擇能夠形成搭配的次短邊長作為一組,有沒有可能本來可以形成兩組,但因為這個貪婪法而錯誤呢?後來爬了 Morris 那邊的方式才意識到得用匈牙利的二分匹配法。
2020-11-04 10:46:21
Not In My Back Yard
我記得 3blue1brown 某個影片有提及(或是隱含)過
不知道是這個
https://www.youtube.com/watch?v=QJYmyhnaaek&ab_channel=3Blue1Brown

還是這個
https://www.youtube.com/watch?v=NaL_Cb42WyY&ab_channel=3Blue1Brown
2020-11-04 14:09:21
Not In My Back Yard
新系統的斷句也太糟糕XD

總之,一時之間也找不到證明佐證這題的貪心是正確的,所以先暫時保留。
2020-11-04 14:10:40

相關創作

更多創作