勾股数公式

by Tanky Woo

at 2010-12-03 11:19:00

original http://www.cnblogs.com/tanky_woo/archive/2010/12/03/1895286.html

话说已经三个月没碰过算法了，真的很无奈，恐怕学到的一点知识全忘光了。

昨天，萝莉神给我一道题目：

Title

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=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

作者: Tanky Woo 发表于 2010-12-03 11:19 原文链接

评论: 2　查看评论　发表评论

最新新闻：
· 2010年十大语义网产品(2010-12-03 18:00)
· 2010十大互联网创业公司问答服务Quora入榜(2010-12-03 17:59)
· 那些让 Web 开发者们深感意外的事情(2010-12-03 17:56)
· 30个灵感来源于动物的创意LOGO设计(2010-12-03 17:53)
· Groupon入华欲收购目标聚焦团宝网(2010-12-03 17:41)

编辑推荐：程序员应知 -- 如何分析海量数据

网站导航：博客园首页我的园子新闻闪存小组博问知识库

Google Reader