• [1426] Secret Polynomial

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • You may have encountered IQ tests with inane questions such as the following: find the next number in the sequence 1, 2, 3, __. Obviously the correct answer is 16, since the sequence lists the values f(1), f(2), f(3), f(4), ..., where f(x) = 2x^3 - 12x^2 + 23x - 12. More generally, given some information about the values of a polynomial, can you find the polynomial? We will restrict our attention to polynomials whose coefficients are all non-negative integers.
  • 输入
  • The first line of input contains an integer 0 < n <= 10000, the number of polynomials to be identified. Each of the next n lines contains two integers, the values f(1) and f(f(1)), where f is the polynomial to be found. Each of these values fits within the range of a signed two's complement 32-bit integer.
  • 输出
  • For each polynomial to be found, output a single line listing its coefficients separated by spaces. Assuming the degree of the polynomial is d, list the d+1 coefficients in descending order of power (i.e. starting with the coefficient of xd and finishing with the coefficient of x0). If the polynomial is the zero polynomial, just output 0. If no polynomial f has the desired values of f(1) and f(f(1)), instead output a line containing the word IMPOSSIBLE. If multiple polynomials f have the desired values of f(1) and f(f(1)), instead output a line containing the word AMBIGUOUS.
  • 样例输入
  • 1
    3 5
    
  • 样例输出
  • 1 2
    
  • 提示
  • 来源
  • 0 0
  • 操作

显示春菜