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

guosl

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

/*
答案：31875000
耗时：0.0000023秒
*/
#include <iostream>
#include <cmath>
using namespace std;

int gcd(int x, int y)//本原直角三角形的两个参数必须互素
{
  if (y == 0)
    return x;
  int z = x % y;
  while (z != 0)
  {
    x = y;
    y = z;
    z = x % y;
  }
  return y;
}

int chk(int n)//检查是否存在边长为k的本原直角三角形
{
  int d = (int)sqrt((double)n);
  for (int i = 1; i <= d; ++i)//枚举本原直角三角形的大参数
  {
    if (n % i == 0)
    {
      int p = n / i;
      if (gcd(i, p) == 1)
      {
        int x = i, y = p - i; //解出本原直角三角形的两个可能的参数
        if (x > y && ((x - y) & 1) != 0)//检查是否合法
        {
          //根据x,y算出本原直角三角形的三个边长
          int a = x * x - y * y;
          int b = 2 * x * y;
          int c = x * x + y * y;
          return a * b * c;
        }
      }
    }
  }
  return 0;
}

int main(void)
{
  for (int k = 1; k <= 22; ++k)//枚举此直角三角形与本原直角三角形的边长倍数
  {
    if (500 % k == 0)
    {
      int p = chk(k);//检查是否存在边长为k的本原直角三角形
      if (p > 0)
      {
        int k1 = (500 / k);
        k1 = k1 * k1 * k1;
        p = p * k1;//存在则保存结果
      }
      if (p == 0)
      {
        p = chk(500 / k);//检查是否存在边长为500/k的本原直角三角形
        if (p > 0)
          p = p * k * k * k;//存在则保存结果
      }
      if (p > 0)
      {
        cout << p << endl;//输出结果
        break;
      }
    }
  }
  return 0;
}

mathtimes

#include <cstdio>
int main()
{
    for(int a=1;a<1000;a++)
        for(int b=1;b<1000;b++)
        {
            int c = 1000-a-b;
            if(c*c==a*a+b*b)
            {
                printf("%d^2 + %d^2 = %d^2",a,b,c);
                return 0;
            }
        }
}

Kazimierz

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

#include <stdio.h>

int main()
{
        int a,b,c;
        for(a=1;a<=1000;a++)
        {
                for(b=1;b<=1000;b++)
                {
                        for(c=1;c<=1000;c++)
                        {
                                if(a*a+b*b==c*c&&a+b+c==1000)
                                {
                                        printf("(%d,%d,%d)",a,b,c);
                                        return 0;
                                }
                        }
                }
        }
}

B1tetheDust

import time

start = time.perf_counter()


class Found(Exception):
    pass


try:
    for a in range(1, 999):
        for b in range(a, 999-a):
            c = 1000 - a - b
            if (a + b < c) or (a + c < b):
                continue
            if (a**2 + b**2 == c**2) or (a**2 + c**2 == b**2):
                print('a * b * c = %d * %d * %d = %d' % (a, b, c, a*b*c))
                raise Found
except Found:
    print('It costs %f s' % (time.perf_counter() - start))

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

Kazimierz

#include <stdio.h>

int main()
{
        int a,b,c;
        for(a=1;a<=1000;a++)
        {
                for(b=1;b<=1000;b++)
                {
                        if((1000-a-b)*(1000-a-b)==(a*a+b*b))
                        {
                                printf("%d %d %d",a,b,1000-a-b);
                                goto end;
                        }
                }
        }
        end:
        return 0;
}

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

Asss-whom

use rayon::prelude::*;
use std::time::Instant;


fn main() {
    let now = Instant::now();
    (1..333i32).for_each(|a| {
        (1..500i32).into_par_iter().for_each(|b| {
            let c = 1000 - a - b;
            if a.pow(2) + b.pow(2) == c.pow(2) {
                println!("a({a}) * b({b}) * c({c}) = {}", a * b * c)
            }
        })
    });
    println!("耗时{}秒。", now.elapsed().as_secs_f32())
}

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

qingyunvi

import time
start = time.time()
for a in range(1, 1000):
    for b in range(a+1, 1000):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(f'a={a}, b={b}, c={c}, number={c**2}')
            break
        else:
            continue
end = time.time()
print(f'time:{end - start}')

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