Tanky WooRSS

勾股数公式

01 Dec 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

话说已经三个月没碰过算法了,真的很无奈,恐怕学到的一点知识全忘光了。 昨天,萝莉神给我一道题目:     

Roowe(没见过这么BT的,拿自己名字去编题目)很喜欢研究数学,现在他就遇到一个有趣的问题,比如,直角三角形的周长是120的话,那么它的三条边可以是20,48,52,或者24,45,51,还有30,40, 50,有三种不同的解,现在他想知道一个区间[a,b]中哪个数的解数最多(1<= a, b <= 1000000)? 输入: 10 100 1000 100000 1 1000000 300000 700000 100000 300000 100000 700000 800000 900000 104 720720 80 360360 1 1000000 输出: 60 2 55440 40 720720 104 360360 80 240240 64 360360 80 831600 78 720720 104 360360 80 720720 104

     让我做下,本来懒得做的,但是他说打表就OK了,于是我就欣然答应了。。。奈何他眼中的打表难易度和我眼中不一样,再次看到了数学系高材生和我的差距,嘿嘿。

     第一次尝试,失败。     我说,不就是勾股定理a^2+b^2=c^2吗?结果他说,你再去补补数学知识。。。。     于是给了我一个链接,我一看,不就是百度百科的勾股数吗,于是就暂时搁浅了。     今晚第二次尝试,仍然失败。     依稀记得昨天他给我说了有个什么勾股数公式,在百度百科那个勾股数的最下面介绍了,但是我看了半天,还是有点迷糊。     然后让他把代码给我看看,好吧,结合百科介绍的勾股数公式,茅塞顿开。

   这里给出勾股数公式:    直角三角形三条边a, b, c,其中a,b是直角边。    则** a=2mn   **

         b=m^2-n^2   

         c=m^2+n^2

当然,这是有前提条件的,也就是其局限性:“勾股数的公式还是有局限的。勾股数公式可以得到所有的基本勾股数,但是不可能得到所有的派生勾股数。比如6,8,10;9,12,15...,就不能全部有公式计算出来”

也就是说,3,4,5可以求出来,但是其倍数6,8,10就不行了。

这里要注意几个问题:

1.构成三角形的条件:

     2mn+m^2-n^2 > m^2+n^2

     既m>n

2.a, b, c互质,即无法得到派生的勾股数。

以下是代码:

// Tanky Woo
// www.WuTianQi.com
#include 
#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;
}