I was recently working on a CodeForce problem

So, I was using SymPy to solve this.

My code is :

from sympy import *

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

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

What I wanted to do:

1. Filter only Positive and integer value from 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)]

CodePudding user response：

I don't think that this is the intended way to solve the code force problem (I think you're just supposed to loop over the possible values for one of the variables).

I'll show how to make use of SymPy here anyway though. Your problem is a diophantine system of equations. Although SymPy has a diophantine solver it only works for individual equations rather than systems.

Usually the idea of using a CAS for something like this though is to symbolically find something like a general result that then helps you to write faster concrete numerical code. Here are your equations with m and n as arbitrary symbols:

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

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

Using the polynomial resultant we can eliminate either x or y from this system to obtain a quartic polynomial for the remaining variable:

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

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

While there is a quartic general formula that SymPy can use (if you use solve or roots here) it is too complicated to be useful for a problem like the one that you are describing. Instead though the rational root theorem tells us that an integer root for y must be a divisor of the constant term:

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

Therefore the possible values for y are:

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]

Since x is m - y**2 the corresponding values for x are:

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]

The candidate solutions are then given by:

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)]

From there you can test which values are solutions:

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)]

The algorithmically minded will probably see from the above example how to make a much more efficient way of implementing the solver.

CodePudding user response：

I've figured out the answer to my question ! At first, I was trying to filter the result from solve(). But there is an easy way to do this.

Sudo Code :

1. solve() gives the intersection point of both Parabolic Equations as a List

2. I just need to filter() the other types of values. Which in my case is <sympy.core.add.Add>

   def rem(_list):
   return list(filter(lambda v: type(v) != Add, _list))
   

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

Final Code :

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", intiger = True, negative = False)
output = []
m,n = input().split(' ')

# I need to solve these 2 equations seperately. 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.

Why I Used This Way :

1. I tried to solve it by Algorithmic way, but it still had some float numbers. I just wanted to skip the loop thing here again !
2. As sympy solve() has already found the values. So, I skipped the other way and focused on filtering !

Sadly, Code Force Compiler showed me a runtime error! I guess it can't import sympy. However, it works fine in VSCode.