ZOJ Problem Set - 2700
Children in school learn how to solve quadratic equations --- that is, equations of form
ax2+bx+c=0,where a , b and c are some given real numbers, and x is the real number to find.
In this problem you have to solve quadratic equation for polynomials with coefficients from Z/2Z . Recall, that there are two numbers in Z/2Z : 0 and 1 , and all operations in this field are performed modulo 2 .
Given polynomials a(t) , b(t) and c(t) , find such polynomial x(t) that
a(t)x2(t)+b(t)x(t)+c(t)=0,where equality should be considered as polynomial equality. Remember, that two polynomials are equal if and only if their coefficients at corresponding powers of t are equal.
There are mutilple cases in the input file.
Each case contains a(t) , b(t) and c(t) , specified as their power followed by their coefficients, starting from the leading one (the coefficient at the greatest power of t ). Zero polynomial has the degree of -1 for the purpose of this problem. Degrees of all polynomials do not exceed 127 .
There is an empty line after each case.
If there is at least one solution to the equation, output any one in the same format, that is used in input. Leading coefficient of the answer polynomial must not be zero. The degree of the polynomial must not exceed 512.
In the other case print no solution on the first line of the output file.
There should be an empty line after each case.
0 1 2 1 1 0 3 1 0 0 0 0 1 1 1 1 0 1 -1 -1 -1
1 1 0 no solution -1
In the first example the equation has the form
x(t)2+(t2+t)x(t)+t3=0,and x(t) = t is clearly a solution.
In the second example the equation is
x(t)2+(t+1)x(t)+1=0,and there is no solution.
In the third example the equation is 0 = 0 and any polynomial is a solution.
Source: Andrew Stankevich's Contest #9