c# - 如何找到三次方程的所有正整数解？

Question

我想找到方程 a^3 + b^3 = c^3 + d^3 的所有正整数解，其中 a, b, c, d 是 1 到 1000

之间的整数

蛮力解决方案继续为每个 (a,b) 对计算所有 (c, d) 对。我想改进这个算法。我只想创建一次 (c,d) 对列表。然后，当我们有一对 (a,b) 时，在 (c,d) 列表中找到匹配项。我们可以通过将每个 (c,d) 对插入从总和映射到该对(或者更确切地说，具有该总和的对列表)的哈希表来快速定位匹配项

n= 1000
for c from 1 to n
    for d from 1 to n
        result = c^3 + d^3
        append (c,d) to list at value map[result]

for a from 1 to n
    for b from 1 to n
        result = a^3 + b^3
        list = map.get(result)
        foreach pair in list
             print a,b, pair

我说我们有 O(n^2) 解吗？为什么？我们如何改进它？什么是 C# 实现？

另外，也许一旦我们有了所有 (c,d) 对的映射，我们就可以直接使用它。我们不需要生成 (a,b) 对。每个 (a,b) 都已经在 map 中。如何实现这个想法？

Answer 1

您可以分组所有可能的总和并打印出包含多个项目的组。这是 O(N**2) 算法:

  // key is sum and value is a list of representations
  Dictionary<int, List<Tuple<int, int>>> solutions = 
    new Dictionary<int, List<Tuple<int, int>>>();

  for (int a = 1; a <= 1000; ++a)
    for (int b = a; b <= 1000; ++b) {
      int sum = a * a * a + b * b * b;

      List<Tuple<int, int>> list = null;

      if (!solutions.TryGetValue(sum, out list)) {
        list = new List<Tuple<int, int>>();

        solutions.Add(sum, list);
      }

      list.Add(new Tuple<int, int>(a, b));
    }

  String report = String.Join(Environment.NewLine,
    solutions.Values
    .Where(list => list.Count > 1) // more than one item
    .Select(list => String.Join(", ", 
      list.Select(item => String.Format("({0}, {1})", item.Item1, item.Item2)))));

  Console.Write(report);

输出(1585行)是

(1, 12), (9, 10)
(1, 103), (64, 94)
(1, 150), (73, 144)
(1, 249), (135, 235)
(1, 495), (334, 438)
...
(11, 493), (90, 492), (346, 428) // <- notice three representations of the same sum
...
(663, 858), (719, 820)
(669, 978), (821, 880)
(692, 942), (720, 926)
(718, 920), (816, 846)
(792, 901), (829, 870)

所以我们有

   1**3 + 12**3 == 9**3 + 10**3
   ...
   11**3 + 493**3 == 90**3 + 492**3 == 346**3 + 428**3   
   ...
   792**3 + 901**3 == 829**3 + 870**3 

有趣的是，我们有 8 三重 表示:

(11, 493), (90, 492), (346, 428)
(15, 930), (198, 927), (295, 920)
(22, 986), (180, 984), (692, 856)
(70, 560), (198, 552), (315, 525)
(111, 522), (359, 460), (408, 423)
(167, 436), (228, 423), (255, 414)
(300, 670), (339, 661), (510, 580)
(334, 872), (456, 846), (510, 828)