整点直角三角形

liangbch

基于27楼，我想出一个方法，不知性能怎样。 考虑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

liangbch

2. // 整点直角三角形, 见http://bbs.emath.ac.cn/thread-2443-1-1.html
3. //
5. #include "stdafx.h"
7. int GCD(int a,int b)
8. {
9. if (a<b)
10. {
11. int t=a; a=b; b=t;
12. }
13. if (b==0)
14. return a;
16. return GCD(b, a%b);
17. }
19. int search_b(int n,int x1,int y1,int *px2,int *py2,int p,int q)
20. {
21. int x2,y2;
22. x2=(n-x1)/p*p;
23. y2= x2/p*q;
24. while ( (x1+x2)*(x1+x2) + (y2-y1)*(y2-y1) >= n*n)
25. {
26. if ( (x1+x2)*(x1+x2) + (y2-y1)*(y2-y1)== n*n)
27. {
28. *px2=x2;
29. *py2=y2;
30. return 1;
31. }
32. x2-=p;
33. y2= x2/p*q;
34. }
35. return 0;
36. }
38. void search(int n)
39. {
40. int x1,y1;
41. int x2,y2;
42. int sn=n*n;
43. int p,q,gcd;
44. int r;
45. int count=0;
46. printf("search integ point for %d\n",n);
47. for (x1=1;x1<n;x1++)
48. {
49. for (y1=1; x1*x1 + y1*y1 <sn; y1++)
50. {
51. gcd=GCD(x1,y1);
52. p = y1/gcd;
53. q = x1/gcd;
54. r=search_b(n,x1,y1,&x2,&y2,p,q);
55. if ( r)
56. {
57. printf( "(%d,%d),(0,0),(%d,%d)\n",-x1,y1,x2,y2); //C点在坐标原点
58. //printf( "(0,%d),(%d,0),(%d,%d)\n",y1,x1,x1+x2,y2); //A点在Y轴
59. count++;
60. }
61. }
62. }
63. if (count==0)
64. {
65. printf("No answer!!!\n");
66. }
67. }
69. int main(int argc, char* argv[])
70. {
71. int i;
73. for (i=2;i<=20;i++)
74. {
75. search(i);
76. }
77. return 0;
78. }

复制代码

mathe

首先，我们需要知道将 $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,比较方便的求所有的解。

mathe

还可以添加(a,b)=1的条件，缩小搜索范围

无心人

wayne: 那个是独立程序，要编译执行的 ghc --make filename.hs

mathe

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)就可以得出总数的公式。

wayne

55# 无心人 还是不行， 是语法问题，

qq.hs:4:26: parse error on input `|'

wayne

由此，将n因子分解以后，解的数目将由n是否是偶数以及n的模4为1的素因子的数目以及它们的次数来决定

嗯，很全，很符合我目前得到的数据

hujunhua

出了几天短差，前天回家时见此热题已有6页了。看到计算程序越来越高效、输出结果越来越精炼，数论分析也越来越豁朗，于是观望了两天，静候mathe的数论公式最终出笼，谁知他兴趣转移到那个极值问题上去了。嘿嘿，那就不等了，我来摘桃了。 要解出数论公式，需要对高斯整数环有一定的了解，刚好是偶比较熟悉的领域。 设n有t个4m+1型素因子，重数依次为k_i, (i=1, 2, ..., t). 那么 1、当n为奇数时，$s(n)=1/2(\prod (4k_i+1)-1)$ 2、当n为偶数时，$s(n)=\prod (4k_i+1)$ 与前面的计算结果不知对得上否。（mathe好快的键盘，我还在与公式和斜体字作斗争，楼下的回复就来了）

mathe

应该太小了