题目75：找出只能以一种方式构成直角三角形的电线长度的数目

欧拉计划

Singular integer right triangles

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

题目：

事实证明 12 cm 是最短的只能够以一种方式弯曲成整数边直角三角形的电线长度。但是还有很多其他例子：

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

与之相反，有一些长度，例如 20cm，不能够弯曲形成整数边的直角三角形。而其他的一些长度则可以以多于一种的方式弯曲成整数边直角三角形；例如，120cm 可以构成三种不同的整数边直角三角形。

120 cm: (30,40,50), (20,48,52), (24,45,51)

L 为电线的长度，对于 L ≤ 1,500,000，有多少个只能以一种方式构成整数边直角三角形？

jerryxjr1220

这题运用了欧几里得公式：
以下是出自wikipedia
Euclid's formula[1] is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers m and n with m > n. The formula states that the integers

a = m^2 - n^2 ,\ \, b = 2mn ,\ \, c = m^2 + n^2
form a Pythagorean triple. The triple generated by Euclid's formula is primitive if and only if m and n are coprime and m − n is odd. If both m and n are odd, then a, b, and c will be even, and so the triple will not be primitive; however, dividing a, b, and c by 2 will yield a primitive triple if m and n are coprime.[2]

Every primitive triple arises from a unique pair of coprime numbers m, n, one of which is even. It follows that there are infinitely many primitive Pythagorean triples. This relationship of a,b and c to m and n from Euclid's formula is referenced throughout the rest of this article.

Despite generating all primitive triples, Euclid's formula does not produce all triples—for example, (9, 12, 15) cannot be generated using integer m and n. This can be remedied by inserting an additional parameter k to the formula. The following will generate all Pythagorean triples uniquely:

a = k\cdot(m^2 - n^2)   ,\ \, b = k\cdot(2mn) ,\ \, c = k\cdot(m^2 + n^2)
where m, n, and k are positive integers with m > n, m − n odd, and with m and n coprime.

That these formulas generate Pythagorean triples can be verified by expanding a2 + b2 using elementary algebra and verifying that the result coincides with c2. Since every Pythagorean triple can be divided through by some integer k to obtain a primitive triple, every triple can be generated uniquely by using the formula with m and n to generate its primitive counterpart and then multiplying through by k as in the last equation.

Many formulas for generating triples with particular properties have been developed since the time of Euclid.

jerryxjr1220

ans =  161667

1. import math  
   
2.   
   
3. L = 1500000  
   
4. maxm = int(math.sqrt(L/2))  
   
5. triple = [0 for x in range(0,L+1)]  
   
6. ans = 0
   
7. 
   
8. for m in range(2,maxm):  
   
9.     for n in range (1,m):  
   
10.         if ((m+n)%2)==1 and math.gcd(m,n)==1:  
    
11.             a=m*m-n*n  
    
12.             b=2*m*n  
    
13.             c=m*m+n*n  
    
14.             p=a+b+c  
    
15.             while p<=L:  
    
16.                 triple[p]=triple[p]+1  
    
17.                 if triple[p]==1:  
    
18.                     ans=ans+1  
    
19.                 if triple[p]==2:  
    
20.                     ans=ans-1  
    
21.                 p=p+a+b+c  
    
22. print('ans = ',ans)

复制代码

najin

用的matlab 结果是
ans =

      161667

时间已过 0.105196 秒。
>>

fc1735

1. from math import gcd
   
2. 
   
3. L = [0] * 1500001
   
4. for n in range(1, int(len(L) ** 0.5) // 2):
   
5.   for m in range(n + 1, 999999999999999999999, 2):
   
6.     if gcd(m, n) != 1:
   
7.       continue
   
8.     l = (m + n) * m * 2
   
9.     if l > len(L):
   
10.       break
    
11.     for i in range(l, len(L), l):
    
12.       L[i] += 1
    
13. 
    
14. print(sum(filter(lambda x: x == 1, L)))
    

复制代码

https://github.com/devinizz/project_euler/blob/master/page02/75.py

guosl

这题我们要用本原直角三角形的结论，具体内容参考：百度百科的本原直角三角形。

1. /*
   
2. 答案：161667
   
3. 耗时：2.28576秒（单核）
   
4.       0.393828秒（六核）
   
5. */
   
6. #include <iostream>
   
7. #include <cmath>
   
8. #include <omp.h>
   
9. using namespace std;
   
10. 
    
11. inline int gcd(int x, int y)//本原直角三角形的两个参数必须互素
    
12. {
    
13.   if (y == 0)
    
14.     return x;
    
15.   int z = x % y;
    
16.   while (z != 0)
    
17.   {
    
18.     x = y;
    
19.     y = z;
    
20.     z = x % y;
    
21.   }
    
22.   return y;
    
23. }
    
24. 
    
25. int chk(int n)//计算边长为n的本原直角三角形的个数
    
26. {
    
27.   n /= 2;
    
28.   int nCount = 0;//计数
    
29.   int d = (int)sqrt((double)n);
    
30.   for (int i = 2; i <= d; ++i)//枚举本原直角三角形的大参数
    
31.   {
    
32.     if (n % i == 0)
    
33.     {
    
34.       int p = n / i;
    
35.       if (gcd(i, p) == 1)
    
36.       {
    
37.         int x = i, y = p - i; //解出本原直角三角形的两个可能的参数
    
38.         if (y > 0 && x > y && ((x - y) & 1) != 0)//检查是否合法
    
39.           ++nCount;//存在计数累加
    
40.       }
    
41.     }
    
42.   }
    
43.   return nCount;//返回计数
    
44. }
    
45. 
    
46. int c[1500001];//c[i]表示周长为i的直角三角形的个数
    
47. 
    
48. int main(void)
    
49. {
    
50.   double t = omp_get_wtime();
    
51.   int nCount = 0;
    
52. #pragma omp parallel shared(c) reduction(+:nCount)
    
53.   {
    
54. #pragma omp for schedule(dynamic)
    
55.     for (int L = 12; L <= 1500000; L += 2)//枚举本原直角三角形的周长（本原直角三角形的周长一定是偶数）
    
56.     {
    
57.       int p = chk(L);//得到边长为L的本原直角三角形的个数
    
58.       int k = 1;
    
59.       while (k*L <= 1500000)
    
60.       {
    
61. #pragma omp atomic        
    
62.         c[L*(k++)] += p;//累加边长为本原直角三角形边长倍数的直角三角形个数
    
63.       }
    
64.     }
    
65. #pragma omp for
    
66.     for (int L = 12; L <= 1500000; L += 2)
    
67.     {
    
68.       if (c[L] == 1)
    
69.         ++nCount;//统计结果
    
70.     }
    
71.   }
    
72.   t = omp_get_wtime() - t;
    
73.   cout << nCount << endl << t << endl;
    
74.   return 0;
    
75. }

复制代码

guosl

这个题目如果用GPU加速则时间更短。

1. /*
   
2. 答案：161667
   
3. 耗时：0.119166秒（GTX970）
   
4. */
   
5. #include <iostream>
   
6. #include <cmath>
   
7. #include <openacc.h>
   
8. using namespace std;
   
9. 
   
10. #pragma acc routine
    
11. inline int gcd(int x, int y)//本原直角三角形的两个参数必须互素
    
12. {
    
13.   if (y == 0)
    
14.     return x;
    
15.   int z = x % y;
    
16.   while (z != 0)
    
17.   {
    
18.     x = y;
    
19.     y = z;
    
20.     z = x % y;
    
21.   }
    
22.   return y;
    
23. }
    
24. 
    
25. #pragma acc routine
    
26. int chk(int n)//计算边长为n的本原直角三角形的个数
    
27. {
    
28.   n /= 2;
    
29.   int nCount = 0;//计数
    
30.   int d = (int)sqrt((double)n);
    
31.   for (int i = 2; i <= d; ++i)//枚举本原直角三角形的大参数
    
32.   {
    
33.     if (n % i == 0)
    
34.     {
    
35.       int p = n / i;
    
36.       if (gcd(i, p) == 1)
    
37.       {
    
38.         int x = i, y = p - i; //解出本原直角三角形的两个可能的参数
    
39.         if (y > 0 && x > y && ((x - y) & 1) != 0)//检查是否合法
    
40.           ++nCount;//存在计数累加
    
41.       }
    
42.     }
    
43.   }
    
44.   return nCount;//返回计数
    
45. }
    
46. 
    
47. int c[1500001];//c[i]表示周长为i的直角三角形的个数
    
48. 
    
49. int main(void)
    
50. {
    
51.   int nCount = 0;
    
52. #pragma acc kernels
    
53.   {
    
54. #pragma acc loop independent
    
55.     for (int L = 12; L <= 1500000; L += 2)//枚举本原直角三角形的周长（本原直角三角形的周长一定是偶数）
    
56.     {
    
57.       int p = chk(L);//得到边长为L的本原直角三角形的个数
    
58.       int k = 1;
    
59.       while (k*L <= 1500000)
    
60.       {
    
61.         int i=L*(k++);
    
62. #pragma acc atomic
    
63.         c[i] += p;//累加边长为本原直角三角形边长倍数的直角三角形个数
    
64.       }
    
65.     }
    
66. #pragma acc loop independent reduction(+:nCount)
    
67.     for (int L = 12; L <= 1500000; L += 2)
    
68.     {
    
69.       if (c[L] == 1)
    
70.         ++nCount;//统计结果
    
71.     }
    
72.   }
    
73.   cout << nCount << endl;
    
74.   return 0;
    
75. }
    

复制代码