【转】一个令人拍案叫绝的算法

在Matrix67的blog 上看的一道题：

有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个整数，黑匣子将返回把这个整数代入多项式后的值。那么，最少需要多少次，我们可以得到这个多项式每项的系数呢？

答案是两次。

第一次，输入 1 ，于是便得到整个多项式的所有系数之和。记作 S 。

第二次，输入 S + 1 ，于是黑匣子返回的是

$a_n * (S + 1)^n + a_{n-1} * (S + 1)^{n-1} + ... + a_1 * (S + 1) + a_0$ 的值。

我们要得到 ${a_n,...,a_0}$ ，只需要把这个值换成 S+1 进制，然后依次读出每一位上的数。

P.S. 第一次得到S是为了保证对于任意系数

---------------------------------------------------------------------------------------

其实最大系数不超过N的多项式，本来就是N进制的本质

作者：Liang Miya
链接：https://www.zhihu.com/question/27547892/answer/131272696
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。