本文主要是介绍FZU 1669 Right-angled Triangle 毕达哥拉斯三元组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【 毕达哥拉斯三元组】
X^2 + Y^2 = Z^2
满足这个方程的的正整数三元组被称为毕达哥拉斯三元组。
本原的毕达哥拉斯三元组,指如果一个毕达哥拉斯三元组x,y,z满足(x,y,z)=1,那么这个毕达哥拉斯三元组称为本原的。
[定理]:正整数x,y,z构成一个本原毕达哥拉斯三元组且y为偶数,当且仅当互素的正整数m,n(m>n),其中m为奇数n为偶数,或者m为偶数n为奇数,并且满足
x=m^2-n^2;
y=2*m*n;
z=m^2+n^2;
那么要求给定的范围内的本原毕达哥拉斯三元组数,只需对m,n分别枚举即可,然后将三元组乘以i(保证i(x+y+z)在给定的范围之内)倍,就可以求出所有满足条件的毕达哥拉斯三元组。
本原的毕达哥拉斯三元组,指如果一个毕达哥拉斯三元组x,y,z满足(x,y,z)=1,那么这个毕达哥拉斯三元组称为本原的。
[定理]:正整数x,y,z构成一个本原毕达哥拉斯三元组且y为偶数,当且仅当互素的正整数m,n(m>n),其中m为奇数n为偶数,或者m为偶数n为奇数,并且满足
x=m^2-n^2;
y=2*m*n;
z=m^2+n^2;
那么要求给定的范围内的本原毕达哥拉斯三元组数,只需对m,n分别枚举即可,然后将三元组乘以i(保证i(x+y+z)在给定的范围之内)倍,就可以求出所有满足条件的毕达哥拉斯三元组。
【例1】 Right-angled Triangle [FZU 1669] 点击打开链接
Problem Description
- A right triangle (or right-angled triangle, formerly called a rectangled triangle) has one 90° internal angle (a right angle). The side opposite to the right angle is the hypotenuse; it is the longest side in the right triangle. The other two sides are the legs or catheti (singular: cathetus) of the triangle. Right triangles conform to the Pythagorean Theorem, wherein the sum of the squares of the two legs is equal to the square of the hypotenuse, i.e., a^2 + b^2 = c^2, where a and b are the legs and c is the hypotenuse.
- An oblique triangle has no internal angle equal to 90°.
- An obtuse triangle is an oblique triangle with one internal angle larger than 90° (an obtuse angle).
- An acute triangle is an oblique triangle with internal angles all smaller than 90° (three acute angles). An equilateral triangle is an acute triangle, but not all acute triangles are equilateral triangles.
Input
Output
Sample Input
Sample Output
Hint
There are five right-angled triangles where a + b + c ≤ 40. That are one right-angled triangle where a = 3, b = 4 and c = 5; one right-angled triangle where a = 6, b = 8 and c = 10; one right-angled triangle where a = 5, b = 12 and c = 13; one right-angled triangle where a = 9, b = 12 and c = 15; one right-angled triangle where a = 8, b = 15 and c = 17.
#include <stdio.h>
#include <string.h>
#include <math.h>long long gcd(long long a,long long b)
{return b==0?a:gcd(b,a%b);
}long long fun(long long a)
{long long i,j,k,tmp,x,y,z,sum=0;tmp=sqrt(a+0.0);for(i=1;i<=tmp;i++){for(j=i+1;j<=tmp;j++){if(2*j*j+2*i*j>a)break;if(i%2!=j%2){if(gcd(i,j)==1){x=j*j-i*i;y=2*i*j;z=i*i+j*j;for(k=1;;k++){if(k*(x+y+z)>a)break;sum++;}}}}}return sum;
}
int main()
{long long n;while(scanf("%lld",&n)!=EOF){long long sum=fun(n);printf("%lld\n",sum);}
}
这篇关于FZU 1669 Right-angled Triangle 毕达哥拉斯三元组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!