K The Right-angled Triangles

链接：https://ac.nowcoder.com/acm/contest/338/K
来源：牛客网

题目描述

Consider the right-angled triangles with sides of integral length.

Give you the integral length of the hypotenuse of a right-angled triangle. Can it construct a right triangle with given hypotenuse c such that the two legs of the triangle are all . integral length?

输入描述:

There are several test cases. The first line contains an integer T(1≤T≤1,000), T is the number of test cases.

The following T lines contain T test cases, each line contains one test case. For each test case, there is an integer : c, the length of hypotenuse.(1≤c≤45,000).

输出描述:

For each case, output Yes if it can construct a right triangle with given hypotenuse c and sides of integral length , No otherwise.

示例1

输入

复制

输出

复制

Yes

No

Yes

Yes

优化一下就可以了

简单题

• 这个题很容易想到的一个思路就是暴力枚举。是 的，我们给的解题方法也是暴力枚举。但是，直 接枚举的复杂度是O(c2)，会超时(TLE)。所以我们 需要将问题转化一下，使得枚举的复杂度是O(c)。

• 如果三角形三边满足如下关系，则是直角三角形。

• a=m2-n2

•b=2mn

• c=m2+n2

• 所以如果斜边长度能够表示成2个正整数的平方和，则能使得三

边都是正整数。这样枚举的复杂度是O（c）。

• 另外，如果斜边长度是一个合数，其有一个因子能表示为2个正 整数的平方和，那么也能使得三边都是正整数。比如c=，有因 子5=+，那么也是可以构成三边全是整数的直角三角形，每边 长度乘以3即可。就是（，，）。

标准答案

•#include <stdio.h>

•#define N 45001

•    int MK[N]={},SQ[];

•    //MK数组标记能否是整数三角形，为0表示不能，非0表示可以，SQ数组记录数的平方值

•int main(){

•    for(i=;i<;++i)SQ[i]=i*i;

•    for(i=;i<;++i)

•    for(j=i+;j<&&(k=SQ[i]+SQ[j])<N;++j)

•    MK[k]=;    //所有能写成2整数平方和的被标记为能

•    for(i=;i<;++i)

•    if(MK[i]==)

•    for(j=;(k=j*i)<N;++j)

•    MK[k]=j;    //所有含2整数平方和的因子的正整数被标记为能

•    scanf("%d",&t);

•while(t--){

•    scanf("%d",&c);

•    printf("%s\n",MK[c]?"Yes":"No");}

•return ;}

#include<stdio.h>

#include<math.h>

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        int flag = 0;

        scanf("%d",&n);

        for(int i = 1; i <= 45000&&i!=n; i++)

        {

            double sum = sqrt(n*n - i*i);

            //    printf("%lf ",sum);

            if(sum - (int)sum < 0.000001)

            {

                flag = 1;

                break;

                //printf("YES\n");

            }

        }

//            if(flag==1)

//            break;

        if(flag == 1)

            printf("Yes\n");

        else

            printf("No\n");

    }

}

巴特西

K The Right-angled Triangles

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章