概念考察題：「多項式和系數」
「行者按：本文（連帶完整答案）首發於zedstudio.org：『多項式和系數』」
多項式和系數
關東行者
有好事者傳了一道題，得空看了一下，考察概念，不錯，推薦給感興趣的朋友：
「 有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个数，黑匣子将返回把这个数代入多项式后的值。那么，最少需要多少次， 我们可以得到这个多项式每项的系数呢？」
友情提示：
關於x的一元（single indeterminate）多項式（Polynomial）p（x），總是可以寫成：
a[n]*x^n + a[n-1]*x^(n-1) + … + a[1]*x^1 + a[0]*x^0
或寫成：
sum[i=0->n](a[i]*x^i）（2）
這裡的[]表示下標，^標示指數，*就是乘法運算，sum是求和運算；作為係數（coefficient）的a[i]是常數（constant），根據原題，它們都是正整數（1，2，3，...）。
一個數是可以用不同的進位系統（位值計數）來表達的，我們日常使用的數多數是十進制數（也有十二進制，六十進制和其它進制的），其基數是10（即可以用0到9這十個數來表達所有的數值，逢十進一）；在計算機中使用的多是二進制（八進制，十六進制），其基數是2（只能用0和1，逢二進一）。
數在位值計數系統中的表達a[n]a[n-1]...a[1]a[0]時（位置從0到n），如果基數是正整數b，則表達成：
a[n]*b^n + a[n-1]*b^(n-1) + … + a[1]*b^1 + a[0]*b^0 （3）
把（3）中的b替換成x，就是前面提到的（1），只是注意這裡的係數a[i] (i=0..n)都小於基數x。
一個具體的例子是十進制的234這個數（n＝2，位置從0到2分別對應：個位，十位和百位），寫成多項式則是：
234 = 2*10^2 + 3*10^1 + 4*10^0
十進制的234按位值計數寫成二進制會是什麼樣子呢？
11101010 ＝ 1*2^7 + 1*2^6 + 1*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0
十進制的234按位值計數寫成八進制會是什麼樣子呢？
352 ＝ 3*8^2 + 5*8^1 + 2*8^0
回到原來的問題，當x賦值1時，（1）給出p(1)：
p(1) ＝ a[n] + a[n-1] + … + a[1] + a[0]
正整數a[i]的和p(1) 還正整數，而且一定大於a[i] (i=0..n)中的任何一個（如果係數是包括零的自然數，p(1)則不一定大於任何一個係數，在下面的取值時就要用p(1)＋1。大家可以想想為什麼。）。
下面要給x賦什麼值才能得出最後的答案呢？思考留給讀者。
（完）