已知直角三角形周長求可能的三角形個數
- 2019 年 11 月 6 日
- 筆記
沒想到我又開始寫博客了，嘿嘿，逛論壇時一個大一小萌新問問題剛好看到，題目雖然簡單但還挺有意思的，如果去年看到肯定給新生加到acm訓練題里，可惜沒機會了。
題目給出直角三角形周長，問有多少種滿足條件的三角形，學過c語言循環的都能兩重循環直接爆出來，但是這道題卡的是時間，1s最高一萬的測試數據，每個數據最大10萬，保險起見複雜度應該降到O(n)。
思路寫到代碼里了，主要利用一些數學關係優化，算法題還是很好玩，以後抽時間做一些leetcode之類的題，順便水博客了。
代碼如下：
1 #include <cstdio> 2 #include <iostream> 3 4 using namespace std; 5 6 int main() 7 { 8 //freopen("out.txt", "w", stdout); 9 int T; 10 cin >> T; 11 while(T--) { 12 long long m; 13 cin >> m; 14 15 //直角三角形三邊關係，短直角邊長度一定小於1/3，可以約束的更狠一點，為了方便我就取1/3了 16 long long maxa = m / 3; 17 18 long long ans = 0; 19 for(long long a = 1; a <= maxa; ++a) { 20 if(a * a % (m - a) != 0) //數學關係，a * a = (c + b) * (c - b) 21 continue; 22 long long b = (m - a - a * a / (m - a)) / 2; //數學關係，已知c + b 和 c - b，很容易求出來c 和 b 23 long long c = m - a - b; 24 //cout << a << ' ' << b << ' ' << c << endl; 25 if(c - a < b && c - b < a && a <= b && a * a + b * b == c * c) //判斷一下是否不合法或者重複 26 ++ans; 27 } 28 cout << ans << endl; 29 } 30 return 0; 31 }
