Secret Polynomial
Time limit1sMemory limit128 MB
Given f(1) and f(f(1)) for an unknown polynomial with non-negative integer coefficients, recover it or report IMPOSSIBLE or AMBIGUOUS.
- Level
Medium6 of 10
- Topics
- Math, Brute force, Implementation
- Solved
- No attempts yet
Problem
You may have seen IQ-test questions such as: find the next number in the sequence 1, 2, 3, __. Supposedly the intended answer is , because the sequence lists for the polynomial . More generally, given some information about the values of a polynomial, can you recover the polynomial? Here we restrict our attention to polynomials whose coefficients are all non-negative integers.
Input
The first line contains an integer (), the number of polynomials to identify. Each of the next lines contains two integers, the values and , where is the polynomial to be found. Each of these values fits within the range of a signed two's-complement 32-bit integer.
Output
For each polynomial, output a single line listing its coefficients separated by spaces. If the polynomial has degree , list its coefficients in descending order of power — starting with the coefficient of and ending with the coefficient of . If the polynomial is the zero polynomial, output just . If no polynomial has the requested values of and , output a line containing the word IMPOSSIBLE instead. If more than one polynomial has the requested values, output a line containing the word AMBIGUOUS instead.