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

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

　　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;

　　}