Polynomial Factoring¶
A polynomial in x of degree D can be written as:
aDxD + aD-1xD-1 + ... + a1x1 + a0
In some cases, a polynomial of degree D can also be written as the product of two polynomials of degrees D1 and D2, where D = D1 + D2. For instance,
4 x2 + 11 x1 + 6 = (4 x1 + 3) * (1 x1 + 2)
In this problem, you will be given two polynomials, denoted F and G. Your task is to find a polynomial H such that G * H = F, and each ai is an integer.
Input¶
You should first read an integer N ≤ 60, the number of test cases. Each test case will start by describing F and then describe G. Each polynomial will start with its degree 0 ≤ D ≤ 20, which will be followed by D+1 integers, denoting a0, a1, ... , aD, where -10000 ≤ ai ≤ 10000. Each polynomial will have a non-zero coefficient for it’s highest order term.
Output¶
For each test case, output a single line describing H. If H has degree DH, you should output a line containing DH + 1 integers, starting with a0 for H. If no H exists such that G * H = F, you should output “no solution”.
Example input¶
5
2 6 11 4
1 3 4
2 1 2 1
1 1 1
2 1 0 -1
1 1 1
1 1 1
2 1 2 1
5 1 1 1 1 1 1
3 1 1 1 1
Example output¶
Case #1: 2 1
Case #2: 1 1
Case #3: 1 -1
Case #4: no solution
Case #5: no solution