黑匣子多项式

有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个整数，黑匣子将返回把这个整数代入多项式后的值。有一个不可思议的 结论：你可以在两步之内还原出整个多项式！这是如何做到的呢？

 

首先，输入 1 ，于是便得到整个多项式的所有系数之和。不妨把这个系数和记作 S 。下一步，输入 S + 1 ，于是黑匣子返回

    an * (S + 1)n + an-1 * (S + 1)n-1 + … + a1 * (S + 1) + a0

把这个值转换成 S + 1 进制，依次读出每一位上的数，它们就是多项式的各项系数了