简述
比较每个三元组的总和,每个三元组的乘积,以及每个三元组所有可能组合的乘积总和。
详细说明
代数基本定理告诉我们,对于一个N次多项式,我们必须有N个根。
利用这个事实,我们将零点设为a1、a2和a3
。现在,我们找到这个多项式的系数。
(x - a1) * (x - a2) * (x - a3)
(x^2 - (a1 + a2) * x + a1a2) * (x - a3)
x^3 - (a1 + a2) * x^2 + (a1a2) * x - a3 * x^2 + (a1a3 + a2a3) * x - a1a2a3
x^3 + (-1 * (a1 + a2 + a3)) * x^2 + (a1a2 + a1a3 + a2a3) * x + (-1 * a1a2a3)
如果两个多项式是等价的,则它们必须具有相同的根(再次使用FTA)。因此我们只需要比较生成的多项式的系数即可。
因此,如果,
(-1 * (a1 + a2 + a3) == (-1 * (b1 + b2 + b3))
---equivalently---
a1 + a2 + a3 == b1 + b2 + b3
和
(a1a2 + a1a3 + a2a3) == (b1b2 + b1b3 + b2b3)
和
-1 * a1a2a3 == -1 * b1b2b3
---equivalently---
a1a2a3 == b1b2b3
那么,我们可以得出三元组 a1, a2, a3
和 b1, b2, b3
是等效的结论。
值得吗?
从实际角度来看,让我们看看这是否确实比 OP 所示的暴力检查更有效。
第一次检查:求和并比较。这需要总共 4 次加法和 1 次相等检查。
检查总数= 5; 运行总数 = 5
第二次检查:乘积、求和和比较。这需要总共 6 次乘法、4 次加法和 1 次相等检查。
检查总数= 11; 运行总数= 16
第三次检查:乘积和比较。这需要总共 4 次乘法和 1 次相等检查。
检查总数= 5; 运行总数= 21
将两个逻辑 AND 操作相加,"生成多项式系数方法"所需的二进制操作总数仅需要:
23 个二进制运算
暴力检查需要总共 18 次相等检查、12 次逻辑 AND 比较和 5 次逻辑 OR 比较,总计:
35 个二进制运算
因此,严格地说,答案是肯定的,"生成多项式系数方法"确实更有效。但是,正如 @WJS 指出的那样,暴力方法有更多的机会进行短路,因此执行得更有效率。
为了完整彻底
我们不能跳过检查每个三元组的所有可能组合的乘积之和。如果我们省略这一点,就会有无数的例子表明这种方法会失败。考虑(23, 32, 45)
和(24, 30, 46)
*:
23 + 32 + 45 = 100
24 + 30 + 46 = 100
23 * 32 * 45 = 33120
24 * 30 * 46 = 33120
它们不相等,但给出相同的和与积。然而,它们不会给出所有可能组合的乘积和相同的总和:
23 * 32 + 23 * 45 + 32 * 45 = 3211
24 * 30 + 24 * 46 + 30 * 46 = 3204
*如果您想了解如何得出类似上面的示例,请先生成长度为3的整数M的所有整数分割,取它们的乘积,找到重复项并选择一对。