在Matrix67的blog 上看的一道题:
有一个黑匣子,黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项,但已知所有的系数都是正整数。每一次,你可以给黑匣子输入一个整数,黑匣子将返回把这个整数代入多项式后的值。那么,最少需要多少次, 我们可以得到这个多项式每项的系数呢?
答案是两次。
第一次,输入 1 ,于是便得到整个多项式的所有系数之和。记作 S 。
第二次,输入 S + 1 ,于是黑匣子返回的是
的值。
我们要得到 ,只需要把这个值换成 S+1 进制, 然后依次读出每一位上的数。
P.S. 第一次得到S是为了保证对于任意系数
---------------------------------------------------------------------------------------
其实最大系数不超过N的多项式,本来就是N进制的本质
作者:Liang Miya
链接:https://www.zhihu.com/question/27547892/answer/131272696
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
原文链接:【转】一个令人拍案叫绝的算法,转载请注明来源!