求解方程a + b + c + d = a*b*c*d

Question

您好我正在尝试解决此方程式中的编程问题,该问题表明您需要执行完整的搜索算法才能找到此结果.

然而,O(N ^ 4)算法需要花费大量时间,因为A,B,C和D的每个值的范围是(0,2000).所以我们可以说A <= B <= C < = d

我想让我的算法更快地将其转换为O(n ^ 3)解决方案.为此,我考虑了A,B和C的某些事情,使算法运行得更快(prunning).但主要的问题是拿出D的搜索,我已经阅读了一些针对类似问题的解决方案以及他们找到的方式D从A + B + C = A*B*C推导它真的很混乱,有人可以解释一下我这个问题的O(N ^ 3)解决方案？非常感谢!

Answer 1

等式

A * B * C * D == A + B + C + D

只有一个解决方案

1 1 2 4

所以时间的复杂性是O(1).

因为A <= B <= C <= D,

A + B + C + D <= 4 * D

于是

A * B * C * D <= 4 * D

和

A * B * C <= 4

因此,仅检查几种组合就足够了:

for(int a = 1; a <= 4; a++)
    for(int b = a; b <= 4; b++)
        for(int c = b; c <= 4; c++)
        {
            // a*b*c*d == a+b+c+d
            // => d == (a+b+c) / (a*b*c - 1)
            if(a * b * c - 1 != 0 && (a + b + c) % (a * b * c - 1) == 0)
            {
                int d = (a + b + c) / (a * b * c - 1);
                if (d >= c)
                    Console.WriteLine("{0} {1} {2} {3}",
                        a, b, c, (a + b + c) / (a * b * c - 1));
            }
        }