黑箱多项式（非负整数系数）需测几点可恢复全部系数

find the values of all the coefficients

专题: General / 综合
难度: L4
来源: QuantQuestion

题目详情

有一个黑箱多项式 $P(x)$ ，其系数都满足 $a_i\ge 0$ （非负整数）。你可以在任意给定点查询 $P(x)$ 的值。

最少需要查询多少个点，才能确定全部系数？

We consider a polynomial $P(x)$ which all coefficients are positive $(a_{i} \geqslant 0)$ . The polynomial is in a black box and we can only retrieve its value in given points. In how many points do we need to value the polynomial in order to find the values of all the coefficients?

解析

最少需要 $\boxed{2}$ 个点。

构造方法：

查询 $P(1)$ ，得到

S=\sum_i a_i.

于是每个系数都满足 $0\le a_i\le S$ 。

再查询 $P(S+1)$ 。因为基数 $B=S+1$ 严格大于每个“数字” $a_i$ ，所以

P(B)=a_0+a_1B+a_2B^2+\cdots

就是该整数在 $B$ 进制下的唯一展开，其各位数字恰好是 $a_0,a_1,a_2,\ldots$ 。

因此两次查询即可恢复所有系数。