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

Question

我想找到方程的所有正整数解,a^3 + b^3 = c^3 + d^3其中a, b, c, d是整数1 to 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)都已经在地图中.如何实现这个想法？

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)