没想到我又开始写博客了, 嘿嘿, 逛论坛时一个大一小萌新问问题刚好看到, 题目虽然简单但还挺有意思的, 如果去年看到肯定给新生加到 acm 训练题里, 可惜没机会了.
题目给出直角三角形周长, 问有多少种满足条件的三角形, 学过 c 语言循环的都能两重循环直接爆出来, 但是这道题卡的是时间, 1s 最高一万的测试数据, 每个数据最大 10 万, 保险起见复杂度应该降到 O(n).
思路写到代码里了, 主要利用一些数学关系优化, 算法题还是很好玩, 以后抽时间做一些 leetcode 之类的题, 顺便水博客了.
代码如下:
- #include <cstdio>
- #include <iostream>
- using namespace std;
- int main()
- {
- //freopen("out.txt", "w", stdout);
- int T;
- cin>> T;
- while(T--) {
- long long m;
- cin>> m;
- // 直角三角形三边关系, 短直角边长度一定小于 1/3, 可以约束的更狠一点, 为了方便我就取 1/3 了
- long long maxa = m / 3;
- long long ans = 0;
- for(long long a = 1; a <= maxa; ++a) {
- if(a * a % (m - a) != 0) // 数学关系, a * a = (c + b) * (c - b)
- continue;
- long long b = (m - a - a * a / (m - a)) / 2; // 数学关系, 已知 c + b 和 c - b, 很容易求出来 c 和 b
- long long c = m - a - b;
- //cout << a << '' << b <<' ' << c << endl;
- if(c - a < b && c - b < a && a <= b && a * a + b * b == c * c) // 判断一下是否不合法或者重复
- ++ans;
- }
- cout << ans << endl;
- }
- return 0;
- }
来源: https://www.cnblogs.com/fan-jiaming/p/11809392.html