SymPy 结果过滤

Question

我最近在开发 CodeForce problem

所以，我使用 SymPy 来解决这个问题。

我的代码是：

from sympy import *

x,y = symbols("x,y", integer = True)
m,n = input().split(" ")

sol = solve([x**2 + y - int(n), y**2 + x - int(m)], [x, y])
print(sol)

我想做的事情：

仅过滤来自SymPy

的正整数

Ex: If I put 14 28 in the terminal it will give me tons of result, but I just want it to show [(5, 3)]

Answer 1

我不认为这是解决代码强制问题的预期方法（我认为您应该只循环遍历其中一个变量的可能值）。

尽管如此，我还是会在这里展示如何使用 SymPy。你的问题是一个丢番图方程组。虽然 SymPy 有一个 diophantine 求解器，但它只适用于单个方程而不是系统。

通常，将 CAS 用于类似这样的事情的想法是象征性地找到类似一般结果的东西，然后帮助您编写更快的具体数字代码。这是你的等式 m 和 n 作为任意符号：

In [62]: x, y, m, n = symbols('x, y, m, n')

In [63]: eqs = [x**2 + y - n, y**2 + x - m]

使用多项式结果，我们可以从该系统中消除 x 或 y，以获得剩余变量的四次多项式：

In [31]: py = resultant(eqs[0], eqs[1], x)

In [32]: py
Out[32]: 
 2        2        4    
m  - 2⋅m⋅y  - n + y  + y

虽然 SymPy 可以使用四次通用公式（如果您在此处使用 solve 或 roots），但它太复杂了，无法解决您所描述的问题.相反，尽管有理根定理告诉我们 y 的整数根必须是常数项的约数：

In [33]: py.coeff(y, 0)
Out[33]: 
 2    
m  - n

因此 y 的可能值为：

In [64]: yvals = divisors(py.coeff(y, 0).subs({m:14, n:28}))

In [65]: yvals
Out[65]: [1, 2, 3, 4, 6, 7, 8, 12, 14, 21, 24, 28, 42, 56, 84, 168]

由于 x 是 m - y**2，因此 x 的对应值为：

In [66]: solve(eqs[1], x)
Out[66]: 
⎡     2⎤
⎣m - y ⎦

In [67]: xvals = [14 - yv**2 for yv in yvals]

In [68]: xvals
Out[68]: [13, 10, 5, -2, -22, -35, -50, -130, -182, -427, -562, -770, -1750, -3122, -7042, -28210]

然后给出候选解决方案：

In [69]: candidates = [(xv, yv) for xv, yv in zip(xvals, yvals) if xv > 0]

In [70]: candidates
Out[70]: [(13, 1), (10, 2), (5, 3)]

从那里您可以测试哪些值是解决方案：

In [74]: eqsmn = [eq.subs({m:14, n:28}) for eq in eqs]

In [75]: [c for c in candidates if all(eq.subs(zip([x,y],c))==0 for eq in eqsmn)]
Out[75]: [(5, 3)]

懂算法的人可能会从上面的例子中看出如何更有效地实现求解器。

Answer 2

我找到问题的答案了！起初，我试图过滤 solve() 的结果。但是有一个简单的方法可以做到这一点。

伪代码：

solve() 给出两个抛物线方程的交点作为 List
我只需要filter()其他类型的值。在我的例子中是 <sympy.core.add.Add>
```
def rem(_list):
return list(filter(lambda v: type(v) != Add, _list))
```

Yes, You can also use type(v) == int

最终代码：

from sympy import *

#  the other values were <sympy.core.add.Add> type. So, I just defined a function to filterOUT these specific types from my list.
def rem(_list):
    return list(filter(lambda v: type(v) != Add, _list))

x,y = symbols("x,y", integer = True, negative = False)
output = []
m,n = input().split(' ')

# I need to solve these 2 equations separately. Otherwise, my defined function will not work without loop.
solX = rem(solve((x+(int(n)-x**2)**2 - int(m)), x))
solY = rem(solve((int(m) - y**2)**2 + y - int(n), y))

if len(solX) == 0 or len(solY) == 0:
    print(0)
else:
    output.extend(solX)      # using "Extend" to add multiple values in the list.
    output.extend(solY)
    print(int((len(output))/2))  # Obviously, result will come in pairs. So, I need to divide the length of the list by 2.

为什么我用这种方式：

我试着用算法的方式解决了，但是还是有一些浮点数。我只是想再次跳过这里的循环！
因为 sympy solve() 已经找到了值。所以，我跳过了另一种方式，专注于过滤！

遗憾的是，code force 编译器显示运行时错误！我猜它不能导入 sympy。但是，它在 VSCode.

中工作正常

SymPy 结果过滤

SymPy result Filtering

sympy

python-3.x