已知直角三角形周长求可能的三角形个数
- 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 }
