黑匣子问题

问题

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

解答

答案是两次。

设 P(x)=An*x^n+An-1*x^(n-1)+...+A1*x^1+A0

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

2. 第二次，输入 S + 1 ，于是黑匣子返回的是 An*(S+1)^n+An-1*(S+1)^(n-1)+...+A1*(S+1)^1+A0

我们要得到 An, An-1, An-2…A1, A0 即将第二次产生的结果转为 S+1 进制，每一位上的结果即为所得。（第一次得到S是确保 对于任意i, 有Ai <= S ）

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