O(n²)解

全部讀入後 先假設第一個是三角形的一邊 假設第二個也是一邊 把三以後的所有邊窮舉看是不是直角三角形

舉完繼續固定第一個 改為第三個當作第二邊 繼續舉 依此類推 複雜度n²/2

判定是不是直角三角形也很簡單 a²+b²==c²就行 不用開根號

O(n²)解 但是加一點優化

一樣窮舉 但是由於這題長度範圍不大 開一個陣列l[101](懶得減1 直接多開一格 而且多做減1還慢)儲存每種長度的木棒出現次數

另一個陣列v儲存不重複的木棒長度(就是讀入長度i發現l[i]==0就加入v)

對v內的元素窮舉計算sqrt(a²+b²) 然後ans+=l[a]*l[b]*l[sqrt(a²+b²)]

O(1)解

由於長度範圍不大 事先找出三邊在100以內的勾股數放到陣列a 讀入木棒跟n²優化的解法一樣放進l 對a內的元素窮舉l[a[k][0]]*l[a[k][1]]*l[a[k][2]] k從0到51

順便附上這個陣列a[52][3]={{3,4,5},{6,8,10},{9,12,15},{12,16,20},{15,20,25},{18,24,30},{21,28,35},{24,32,40},{27,36,45},{30,40,50},{33,44,55},{36,48,60},{39,52,65},{42,56,70},{45,60,75},{48,64,80},{51,68,85},{54,72,90},{57,76,95},{60,80,100},{5,12,13},{10,24,26},{15,36,39},{20,48,52},{25,60,65},{30,72,78},{35,84,91},{8,15,17},{16,30,34},{24,45,51},{32,60,68},{40,75,85},{7,24,25},{14,48,50},{21,72,75},{28,96,100},{9,40,41},{18,80,82},{11,60,61},{12,35,37},{24,70,74},{13,84,85},{16,63,65},{20,21,29},{40,42,58},{60,63,87},{28,45,53},{33,56,65},{36,77,85},{39,80,89},{48,55,73},{65,72,97}};

python的陣列是這樣,方便copy

a=[        [3,4,5],[6,8,10],[9,12,15],[12,16,20],[15,20,25],[18,24,30],[21,28,35],[24,32,40],[27,36,45],[30,40,50],[33,44,55],[36,48,60],[39,52,65],[42,56,70],[45,60,75],[48,64,80],[51,68,85],[54,72,90],[57,76,95],[60,80,100],[5,12,13],[10,24,26],[15,36,39],[20,48,52],[25,60,65],[30,72,78],[35,84,91],[8,15,17],[16,30,34],[24,45,51],[32,60,68],[40,75,85],[7,24,25],[14,48,50],[21,72,75],[28,96,100],[9,40,41],[18,80,82],[11,60,61],[12,35,37],[24,70,74],[13,84,85],[16,63,65],[20,21,29],[40,42,58],[60,63,87],[28,45,53],[33,56,65],[36,77,85],[39,80,89],[48,55,73],[65,72,97]]
O(1)解

由於長度範圍不大 事先找出三邊在100以內的勾股數放到陣列a 讀入木棒跟n²優化的解法一樣放進l 對a內的元素窮舉l[a[k][0]]*l[a[k][1]]*l[a[k][2]] k從0到51

順便附上這個陣列a[52][3]={{3,4,5},{6,8,10},{9,12,15},{12,16,20},{15,20,25},{18,24,30},{21,28,35},{24,32,40},{27,36,45},{30,40,50},{33,44,55},{36,48,60},{39,52,65},{42,56,70},{45,60,75},{48,64,80},{51,68,85},{54,72,90},{57,76,95},{60,80,100},{5,12,13},{10,24,26},{15,36,39},{20,48,52},{25,60,65},{30,72,78},{35,84,91},{8,15,17},{16,30,34},{24,45,51},{32,60,68},{40,75,85},{7,24,25},{14,48,50},{21,72,75},{28,96,100},{9,40,41},{18,80,82},{11,60,61},{12,35,37},{24,70,74},{13,84,85},{16,63,65},{20,21,29},{40,42,58},{60,63,87},{28,45,53},{33,56,65},{36,77,85},{39,80,89},{48,55,73},{65,72,97}};

AC (2ms, 76KB)