如何确定x和y是否存在于满足等式的整数X集合中

Question

我在准备考试的时候遇到了考试问题而且我坚持了下来.问题是:

设计一种算法,给定一组正整数X,确定方程x ⁵ + xy-y ² = y ³是否具有x和y都属于X的解.

没有涉及编程,只是算法设计.有人可以分享他们的想法吗？

蛮力是不可接受的

Answer 1

伪代码：

result = false
foreach (x in X) {
    foreach (y in X) {
        if (x^5 + x*y - y^2 == y^3) result = true
    }
}

有比预期更复杂的事情吗？如果是这样，我们可以利用高阶项，x^5如下所示：

Sort X as a list from least to greatest.
result = false
foreach (y in X) {
    v = y*y*(y+1)
    foreach (x in X) {
        x2 = x*x
        u = x2*x2 + x*y - v
        if (u == 0) {
            result = true
            goto [DONE]
        }
        if (u > 0) goto [NEXT]
    }
    [NEXT]
}
[DONE]