在给定范围内找到方程 x² + y² = z² 的解的复杂度最高的算法是什么？
x、y、z均为整数，取值范围约为[0,10^6]。
我能做的最好的事情就是遍历所有 x 和所有 y 并将 x² + y² 存储在散列中，然后遍历所有可能的 z 并检查 z² 是否在散列中。
最佳答案
可以只考虑x是奇数，y是偶数。
x 和 y 的解甚至可以通过注意以下内容获得:
x = 2x1; y = 2y1; z = 2z1，其中x1、y1、z1也是一个解
你可以很容易地证明，如果 x 和 y 都是奇数，则 x^2+y^2 给出余数 2 模 4，这不可能是一个完美的正方形。
显然，如果 (x,y,z) 是解，则 (y,x, z) 也是解
通过此优化，您考虑 x 和 y 的可能性减少 4 倍，而 z 的可能性仅为奇数(减少 2 倍)。
关于algorithm - 找到 x^2+y^2=z^2 解决方案的最佳复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47134597/