讓我做下，本來懶得做的，但是他說打表就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