考虑2种情况
1. 直角三角形的直角顶点C在坐标原点，另外2个点分别在横坐标和纵坐标轴上。这样的点可以直接够枚举出来，其坐标是勾股数.勾股数有很多如（3，4,5),(12,5,13)这个就不用多说了。
2. 将三角形直角顶点C置于坐标原点,A点置于第2象限,(x<0,y>0), B点置于第一象限(x>0,y>0). 对A点,枚举坐标(x1,y1), 使得 -n<x1<0, 0<y1<n, x1^2+y1^2<=n^2. 容易知道,最多需要n^2次。以下为详细的步骤。
2.1 枚举一个点A,其坐标为(x1,y1), 使得 -n<x1<0, 0<y1<n, x1^2 + y1^2 < n^2.
2.2 对于每1个A(x1,y1),检查是否存在点B,使得 |AB|=n。 方法：
若OA的斜率表示为p/q =y1/x1(p/q是一个既约分数),容易知道线段OB的斜率是1/k=q/p,因为B的坐标是整点坐标,则B的x坐标必须是p的倍数。
步骤 2.2.1: 找出一个B,其横坐标X2,使得X2满足 X2+|x1|刚好小于n且X2是p的的倍数.
步骤 2.2.2: 求B的纵坐标Y2=X2*q/p. 如B和A点距离是n,则得到一个解,如果B和A点距离小于n,则这样的A点没有解。继续尝试下一个A点,转步骤2.1。
步骤 2.2.3x2-=p,转步骤2.2.2,尝试找出符合条件的B点。
说明：
1. 通常情况下，步骤2.2.2 和 2.2.3应该只需执行有限的几步，因为枚举A点总共之多需要n*n次，故总的复杂度为O(n*n).
2. 这里A点的横坐标为负数,将三角形向右平移x1个单位,则三角想所有的点都是正数了。
// 整点直角三角形, 见http://bbs.emath.ac.cn/thread-2443-1-1.html
//
#include "stdafx.h"
int GCD(int a,int b)
{
if (a<b)
{
int t=a; a=b; b=t;
}
if (b==0)
return a;
return GCD(b, a%b);
}
int search_b(int n,int x1,int y1,int *px2,int *py2,int p,int q)
{
int x2,y2;
x2=(n-x1)/p*p;
y2= x2/p*q;
while ( (x1+x2)*(x1+x2) + (y2-y1)*(y2-y1) >= n*n)
{
if ( (x1+x2)*(x1+x2) + (y2-y1)*(y2-y1)== n*n)
{
*px2=x2;
*py2=y2;
return 1;
}
x2-=p;
y2= x2/p*q;
}
return 0;
}
void search(int n)
{
int x1,y1;
int x2,y2;
int sn=n*n;
int p,q,gcd;
int r;
int count=0;
printf("search integ point for %d\n",n);
for (x1=1;x1<n;x1++)
{
for (y1=1; x1*x1 + y1*y1 <sn; y1++)
{
gcd=GCD(x1,y1);
p = y1/gcd;
q = x1/gcd;
r=search_b(n,x1,y1,&x2,&y2,p,q);
if ( r)
{
printf( "(%d,%d),(0,0),(%d,%d)\n",-x1,y1,x2,y2); //C点在坐标原点
//printf( "(0,%d),(%d,0),(%d,%d)\n",y1,x1,x1+x2,y2); //A点在Y轴
count++;
}
}
}
if (count==0)
{
printf("No answer!!!\n");
}
}
int main(int argc, char* argv[])
{
int i;
for (i=2;i<=20;i++)
{
search(i);
}
return 0;
}
首先，我们需要知道将
$n^2=X^2+Y^2$的所有分解方案，
这个通过对n的因子分解可以做到，可以参考:http://blog.csdn.net/mathe/archive/2007/06/06/1641160.aspx
其次
对于任意的这样三角形，我们总可以将直角的顶点移动到原点，假设另外两点坐标为
$(ua,ub),(-vb,va)$,那么$n^2=(u^2+v^2)(a^2+b^2)$,
于是我们的目的就是将$n^2$表示成两个可以表示成两个都可以表示成双整数平方和的乘积就可以了，其中a,b之一可以是0，但是u,v都不可以是0.用这个方法，可以对每个n,比较方便的求所有的解。 还可以添加(a,b)=1的条件，缩小搜索范围 wayne:
那个是独立程序，要编译执行的
ghc --makefilename.hs 54#的表示方法可以改成
$n^2=d^2(u^2+v^2)(a^2+b^2)$,
其中(a,b)=1,(u,v)=1,u>0,v>0.
由此，将n因子分解以后，解的数目将由n是否是偶数以及n的模4为1的素因子的数目以及它们的次数来决定
比如39只含有一个模4为1的素因子，所以n=39和n=17的解的数目是相同的。
对于每个n,其中模4为3的素因子必然归入d所在的项，而对于因子2，要么$u^2+v^2$和$a^2+b^2$同时使用了一个2（也就是$2=(1+i)(1-i)$），要么它们同时不使用2，也就是d中2的次数要么同n相同，要么比n次数低一个。
而同样，对于所有其它的模4为1的素因子，如果它的总次数为2k次，我们等于将它分成3部分：假设
$p=s^2+t^2$,我们将其中部分次数划分到$u^2+v^2$这一项，可以写成$(s+ti)^u(s-ti)^u$或$(s-ti)^u(s+ti)^u$,同样一部分归入$a^2+b^2$这一项，可以写成$(s+ti)^v(s-ti)^v$,余下保留在d^2中,于是可以写成$2k=u+v+(2k-u-v)$其中u+v必须是偶数。
而对于每个这样的划分，如果u或v不是0,我们还有其顺序安排的选择，即可以选择$(s+ti)^u(s-ti)^u$或$(s-ti)^u(s+ti)^u$。这样，对于每个次数k,我们可以事先计算出其对应的数目f(k),这个函数应该可以比较容易推导出来（可能是k的二次函数?）
然后对于每个素因子，把它们对应的f(k)相乘，最后去除一种特素情况（会导致u=0或v=0)就可以得出总数的公式。 55# 无心人
还是不行，
是语法问题，
qq.hs:4:26: parse error on input `|' 由此，将n因子分解以后，解的数目将由n是否是偶数以及n的模4为1的素因子的数目以及它们的次数来决定
嗯，很全，很符合我目前得到的数据
斜边长为n的不全等的整点直角三角形的计数s(n)。
本帖最后由 hujunhua 于 2010-6-16 16:09 编辑出了几天短差，前天回家时见此热题已有6页了。看到计算程序越来越高效、输出结果越来越精炼，数论分析也越来越豁朗，于是观望了两天，静候mathe的数论公式最终出笼，谁知他兴趣转移到那个极值问题上去了。嘿嘿，那就不等了，我来摘桃了。
要解出数论公式，需要对高斯整数环有一定的了解，刚好是偶比较熟悉的领域。
设n有t个4m+1型素因子，重数依次为ki, (i=1, 2, ..., t). 那么
1、当n为奇数时，s(n)=1/2(\prod (4k_i+1)-1)
2、当n为偶数时，s(n)=\prod (4k_i+1)
与前面的计算结果不知对得上否。（mathe好快的键盘，我还在与公式和斜体字作斗争，楼下的回复就来了） 应该太小了