早上好,我是新来的,我带来了一个小问题。我无法针对以下问题开发有效的算法: 我需要找到三个正数 x、y 和 z 的组合,以便 x + y、x - y、y + z、y - z、x + z 和 x - z 是完全平方数。 问题是开发一种算法,找到 1 之间的 x、y 和 z 的所有组合 和 2,000,000。
目前我在 for
中使用 for
肯定不会在我有孙子之前结束。
最佳答案
以替换开始的基本思想,例如:
u = x + y
v = x - y
w = y + z
那么 x + y, x - y, y + z, y - z, x + z and x - z 就变成了
u, v, w, u - v - w, v + w, u - w [all have to be squares]
然后用另一个替换,u = a², v = b², w = c²,你得到:
a², b², c², a² - b² - c², b² + c², a² - c² [all have to be squares]
现在您可以枚举所有可能已经足够快的 a、b、c-s。
进一步的想法可能是首先使用 Pythagorean triples 枚举所有 b²、c²、b²+c² (通过将其代入 m 和 n,枚举所有互质数 (m,n),然后使用欧几里得公式)然后以类似的方式找到给定的 (b,c) the as(例如,将 a² - c² = x² 更改为 a² = x² + c² 并再次使用三元组)。
关于algorithm - 三个正数 x、y、z 的组合,使得 x + y、x - y、y + z、y - z、x + z 和 x - z 是完全平方数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15339256/