题目9：找出唯一的满足a + b + c = 1000的毕达哥拉斯三元组{a, b, c}

guosl

本题可以应用本原直角三角形的参数形式来解。

1. /*
   
2. 答案：31875000
   
3. 耗时：0.0000023秒
   
4. */
   
5. #include <iostream>
   
6. #include <cmath>
   
7. using namespace std;
   
8. 
   
9. int gcd(int x, int y)//本原直角三角形的两个参数必须互素
   
10. {
    
11.   if (y == 0)
    
12.     return x;
    
13.   int z = x % y;
    
14.   while (z != 0)
    
15.   {
    
16.     x = y;
    
17.     y = z;
    
18.     z = x % y;
    
19.   }
    
20.   return y;
    
21. }
    
22. 
    
23. int chk(int n)//检查是否存在边长为k的本原直角三角形
    
24. {
    
25.   int d = (int)sqrt((double)n);
    
26.   for (int i = 1; i <= d; ++i)//枚举本原直角三角形的大参数
    
27.   {
    
28.     if (n % i == 0)
    
29.     {
    
30.       int p = n / i;
    
31.       if (gcd(i, p) == 1)
    
32.       {
    
33.         int x = i, y = p - i; //解出本原直角三角形的两个可能的参数
    
34.         if (x > y && ((x - y) & 1) != 0)//检查是否合法
    
35.         {
    
36.           //根据x,y算出本原直角三角形的三个边长
    
37.           int a = x * x - y * y;
    
38.           int b = 2 * x * y;
    
39.           int c = x * x + y * y;
    
40.           return a * b * c;
    
41.         }
    
42.       }
    
43.     }
    
44.   }
    
45.   return 0;
    
46. }
    
47. 
    
48. int main(void)
    
49. {
    
50.   for (int k = 1; k <= 22; ++k)//枚举此直角三角形与本原直角三角形的边长倍数
    
51.   {
    
52.     if (500 % k == 0)
    
53.     {
    
54.       int p = chk(k);//检查是否存在边长为k的本原直角三角形
    
55.       if (p > 0)
    
56.       {
    
57.         int k1 = (500 / k);
    
58.         k1 = k1 * k1 * k1;
    
59.         p = p * k1;//存在则保存结果
    
60.       }
    
61.       if (p == 0)
    
62.       {
    
63.         p = chk(500 / k);//检查是否存在边长为500/k的本原直角三角形
    
64.         if (p > 0)
    
65.           p = p * k * k * k;//存在则保存结果
    
66.       }
    
67.       if (p > 0)
    
68.       {
    
69.         cout << p << endl;//输出结果
    
70.         break;
    
71.       }
    
72.     }
    
73.   }
    
74.   return 0;
    
75. }

复制代码

mathtimes

1. #include <cstdio>
   
2. int main()
   
3. {
   
4.     for(int a=1;a<1000;a++)
   
5.         for(int b=1;b<1000;b++)
   
6.         {
   
7.             int c = 1000-a-b;
   
8.             if(c*c==a*a+b*b)
   
9.             {
   
10.                 printf("%d^2 + %d^2 = %d^2",a,b,c);
    
11.                 return 0;
    
12.             }
    
13.         }
    
14. }

复制代码

Kazimierz

答案(200,375,425) 循环嵌套穷举即可

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int a,b,c;
   
6.         for(a=1;a<=1000;a++)
   
7.         {
   
8.                 for(b=1;b<=1000;b++)
   
9.                 {
   
10.                         for(c=1;c<=1000;c++)
    
11.                         {
    
12.                                 if(a*a+b*b==c*c&&a+b+c==1000)
    
13.                                 {
    
14.                                         printf("(%d,%d,%d)",a,b,c);
    
15.                                         return 0;
    
16.                                 }
    
17.                         }
    
18.                 }
    
19.         }
    
20. }
    

复制代码

B1tetheDust

1. import time
   
2. 
   
3. start = time.perf_counter()
   
4. 
   
5. 
   
6. class Found(Exception):
   
7.     pass
   
8. 
   
9. 
   
10. try:
    
11.     for a in range(1, 999):
    
12.         for b in range(a, 999-a):
    
13.             c = 1000 - a - b
    
14.             if (a + b < c) or (a + c < b):
    
15.                 continue
    
16.             if (a**2 + b**2 == c**2) or (a**2 + c**2 == b**2):
    
17.                 print('a * b * c = %d * %d * %d = %d' % (a, b, c, a*b*c))
    
18.                 raise Found
    
19. except Found:
    
20.     print('It costs %f s' % (time.perf_counter() - start))
    

复制代码

运行结果：
a * b * c = 200 * 375 * 425 = 31875000
It costs 0.051990 s
偶然间犯了一个错发现：把continue改为break甚至会更快

Kazimierz

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int a,b,c;
   
6.         for(a=1;a<=1000;a++)
   
7.         {
   
8.                 for(b=1;b<=1000;b++)
   
9.                 {
   
10.                         if((1000-a-b)*(1000-a-b)==(a*a+b*b))
    
11.                         {
    
12.                                 printf("%d %d %d",a,b,1000-a-b);
    
13.                                 goto end;
    
14.                         }
    
15.                 }
    
16.         }
    
17.         end:
    
18.         return 0;
    
19. }
    

复制代码

这几天在看自己以前写的代码，才发现优化空间很大
time：0.03025s

Asss-whom

1. use rayon::prelude::*;
   
2. use std::time::Instant;
   
3. 
   
4. 
   
5. fn main() {
   
6.     let now = Instant::now();
   
7.     (1..333i32).for_each(|a| {
   
8.         (1..500i32).into_par_iter().for_each(|b| {
   
9.             let c = 1000 - a - b;
   
10.             if a.pow(2) + b.pow(2) == c.pow(2) {
    
11.                 println!("a({a}) * b({b}) * c({c}) = {}", a * b * c)
    
12.             }
    
13.         })
    
14.     });
    
15.     println!("耗时{}秒。", now.elapsed().as_secs_f32())
    
16. }

复制代码

---
a(200) * b(375) * c(425) = 31875000
耗时0.0070322秒。

qingyunvi

1. import time
   
2. start = time.time()
   
3. for a in range(1, 1000):
   
4.     for b in range(a+1, 1000):
   
5.         c = 1000 - a - b
   
6.         if a**2 + b**2 == c**2:
   
7.             print(f'a={a}, b={b}, c={c}, number={c**2}')
   
8.             break
   
9.         else:
   
10.             continue
    
11. end = time.time()
    
12. print(f'time:{end - start}')

复制代码

a=200, b=375, c=425, number=180625
time:0.4737279415130615

HuangBin2025

1. for i in range(1,333):
   
2.     for j in range(i+1,500):
   
3.         if i*i+j*j==(1000-i-j)*(1000-i-j):
   
4.             print(i*j*(1000-i-j))

复制代码