让我做下，本来懒得做的，但是他说打表就OK了，于是我就欣然答应了。。。奈何他眼中的打表难易度和我眼中不一样，再次看到了数学系高材生和我的差距，嘿嘿。
第一次尝试，失败。
我说，不就是勾股定理a^2+b^2=c^2吗？结果他说，你再去补补数学知识。。。。
于是给了我一个链接，我一看，不就是百度百科的勾股数吗，于是就暂时搁浅了。
今晚第二次尝试，仍然失败。
依稀记得昨天他给我说了有个什么勾股数公式，在百度百科那个勾股数的最下面介绍了，但是我看了半天，还是有点迷糊。
然后让他把代码给我看看，好吧，结合百科介绍的勾股数公式，茅塞顿开。
这里给出勾股数公式：
直角三角形三条边a, b, c，其中a,b是直角边。
则 a=2*m*n
b=m^2-n^2
c=m^2+n^2
当然，这是有前提条件的，也就是其局限性：“勾股数的公式还是有局限的。勾股数公式可以得到所有的基本勾股数，但是不可能得到所有的派生勾股数。比如6，8，10；9，12，15…，就不能全部有公式计算出来”
也就是说，3,4,5可以求出来，但是其倍数6,8,10就不行了。
这里要注意几个问题：
1.构成三角形的条件：
2*m*n+m^2-n^2 > m^2+n^2
既m>n
2.a, b, c互质，即无法得到派生的勾股数。
以下是代码：
// Tanky Woo
// www.WuTianQi.com
#include <iostream>
#define M 1000000
int arr[M+1];
using namespace std;
int gcd(int a, int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
void init()
{
for(int i=1; i<=800; ++i)
for(int j=i+1; 2*j*j+2*j*i<=M; ++j)
{
int x, y, z;
x=2*i*j;
y=j*j-i*i;
z=j*j+i*i;
//确保x,y,z互质
if(gcd(gcd(x, y), z) == 1)
{
int t = x+y+z;
int tmp = 1;
while(tmp*t <= M)
{
arr[tmp*t]++;
++tmp;
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
init();
int n, m;
while(scanf("%d%d",&n,&m) != EOF){
int pos = 0;
int Max = 0;
for(int i=n; i<=m; i++){
if(arr[i] > Max){
Max = arr[i];
pos = i;
}
}
printf("%d %d\n",pos, Max);
}
return 0;
}
Tanky Woo原创，转载请注明： 转载自Tanky Woo
文章标题: 勾股数公式
本文链接地址: http://www.wutianqi.com/?p=1632