勾股数公式

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

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互质,即无法得到派生的勾股数。

以下是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 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,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《勾股数公式》有56个想法

      1. @Tanky Woo,
        xiaozhou.net那位是个牛人啊,曾经得过MS MVP,而且在MS工作了几年,现在才27
        04年本科毕业,两年后结婚,现在孩子1.5岁,有房有车,家住成都XXX区XXX街道XXX号…… [s:6]

  1. 话说搜起来比较麻烦。。

    话说如何避免无效解类?话说要卡限制条件。。话说如何卡的更多类?话说想想纠结下。。

    话说程序中大约O(N^2)(我没仔细算,不知道对不对)的时间复杂度貌似有点小高。。话说维护一个表吧,把范围和结果关联起来,应该能减少极多的搜索量。话说数据中应该有很多重复数据和重复运算。

发表评论

电子邮件地址不会被公开。 必填项已用*标注