趣题：两步猜出多项式的各项系数

来源: Matrix67

---

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

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

    a_n * (S + 1)ⁿ + a_n-1 * (S + 1)^n-1 + … + a₁ * (S + 1) + a₀

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

来源：http://rjlipton.wordpress.com/2010/12/20/some-mathematical-gifts/
这个有趣的问题曾经以另一形式出现在了这个 Blog 里，见 这里 的 35 题。