链接：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
输入
复制4 5 6 15 13
输出
复制Yes No Yes Yes
优化一下就可以了
简单题
• 这个题很容易想到的一个思路就是暴力枚举。是 的，我们给的解题方法也是暴力枚举。但是，直 接枚举的复杂度是O(c2)，会超时(TLE)。所以我们 需要将问题转化一下，使得枚举的复杂度是O(c)。 • 如果三角形三边满足如下关系，则是直角三角形。 • a=m2-n2 •b=2mn • c=m2+n2 • 所以如果斜边长度能够表示成2个正整数的平方和，则能使得三 边都是正整数。这样枚举的复杂度是O（c）。 • 另外，如果斜边长度是一个合数，其有一个因子能表示为2个正 整数的平方和，那么也能使得三边都是正整数。比如c=15，有因 子5=12+22，那么也是可以构成三边全是整数的直角三角形，每边 长度乘以3即可。就是（9，12，15）。
标准答案
•#include <stdio.h> •#define N 45001 • int MK[N]={0},SQ[213]; • //MK数组标记能否是整数三角形，为0表示不能，非0表示可以，SQ数组记录数的平方值 •int main(){ • for(i=1;i<213;++i)SQ[i]=i*i; • for(i=1;i<213;++i) • for(j=i+1;j<213&&(k=SQ[i]+SQ[j])<N;++j) • MK[k]=1; //所有能写成2整数平方和的被标记为能 • for(i=5;i<22501;++i) • if(MK[i]==1) • for(j=2;(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 0;}
#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");elseprintf("No\n");} }
