SDNU 1147 Pythagoras's Revenge 【技巧暴力】

发表于 | 更新于 | 分类于

题目链接：

SDNU 1147 Pythagoras’s Revenge

题目大意：

给定直角三角形的一直角边，求出各边均为整数的以它为最小边的直角三角形的个数

解题思路：

一、【真丶暴力】

根据勾股定理可知$a^2+b^2=c^2$我们试着让b从等于a+1开始枚举可能的解，如果枚举出来的c是整数的话，让ans++，最后输出ans。

然而这样枚举的终止条件是什么呢？$10 \times a$ ？ $100 \times a $？ $1000 \times a$ ？ 我一直试到了$10000 \times a​$还是求不全。 显然这样是不行的。

二、【技巧丶暴力】

对于$a^2+b^2=c^2$，我们移项可得$a^2=c^2-b^2$，再化，可得$a^2 = (c-b) \times (c+b)$。根据三角形任意两边之和大于第三边、任意两边之差小于第三边可知，令$i=c-b$, $j=c+b$，即$i$ < $a$、$j$ > $a$，且$j - i = 2b$。接下来枚举i就可以了。

Mycode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int main()
{
    LL a, b, ans;
    while(scanf("%lld",&a) && a)
    {
        ans = 0;
        for(LL i = 1; i < a; ++i)
        {
            if(a * a % i == 0)
            {
                LL j = a * a / i;
                if((j-i) % 2 == 0)
                {
                    b = (j-i) / 2;
                    if(b > a)
                        ++ans;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}
Donate comment here
0%