有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个整数，黑匣子将返回把这个整数代入多项式后的值。有一个不可思议的结论：你可以在两步之内还原出整个多项式！这是如何做到的呢？
首先，输入 1 ，于是便得到整个多项式的所有系数之和。不妨把这个系数和记作 S 。下一步，输入 S + 1 ，于是黑匣子返回
an * (S + 1)n + an-1 * (S + 1)n-1 + … + a1 * (S + 1) + a0
把这个值转换成 S + 1 进制，依次读出每一位上的数，它们就是多项式的各项系数了。
来源：http://rjlipton.wordpress.com/2010/12/20/some-mathematical-gifts/
这个有趣的问题曾经以另一形式出现在了这个 Blog 里，见 这里 的 35 题。
沙发么？
还真是
我也是差不多的想法，先输入1，得到系数和S，然后输入10^(s+1)……
差不多，我想的是先输入1，得到各系数之和，记为S，再输入大于S的某个10的n次方。然后结果按照每n个数断位即可。
请教一下，为什么要求各系数之和呢，没想明白？直接输入任意是N，然后换为N进制，与这个有什么不同吗？
@AK 你不能保证你的N比S大
呃，应该是说不能保证N比每一个系数大
弱弱一问，我们通过2个方程得到了N个未知数，隐含的N-2个条件在哪？
@error 404
实际上是N个方程.
@error 404:
n个方程n个未知数是建立在给定方程的基础上的。
自己选定方程的话就不同了
突然想到，这是不是某种压缩算法。。。
然后再想到，输入S+1后产生的结果（称为SS）的长度可能（而且大多）比储存所有a[n]的长度还要大。。。
eg:
不妨设所有数字都以1位高精的方式存储。
9、1、1、1、1、1、1、1 共占8
S=16 储存 占2
SS=3718694224 储存 占10
共占12
而且SS随着a[n]项数的增加而增加的速度很快。
不错~
嗯，不错~
这里是否有个错误？直观上看，存在一个潜规则，那就是ai(s+1)，则不能得出所有系数。
谢谢分享，很有意思的题目。
不错,启发思维
如果知道系数的最大值，那么只要一步就可以做到了~
谢谢 很好的题目~~ matrix真是大牛啊
如果条件不限制在正整数是否可以用一步就得出结论呢？
比如输入个0.10100……01……什么的，适当构造0增加的速度，然后小数点后足够多位后会不会就能直接反向得到那个系数？
如果条件不限制输入的数字为正整数是否可以用一步就得出结论呢？
比如输入个0.10100……01……什么的，适当构造0增加的速度，然后小数点后足够多位后会不会就能直接反向得到那个系数？
恩，比想象的要简单。
进一步，求出的这个多项式是唯一的吗？
回sqybi ：个系数是正数故s不小于任何一个系数
回复“地基”“15楼”：由于每个系数是正数故s不小于任何一个系数。
我的疑问是：N个未知数，只有两个独立方程。难道条件“所有系数是正整数”就代替了其他N-2个方程？或者，这仅仅是数制上的巧合？
“18楼”的意思是代入一个比最大系数大的数（记m）就行，然后继续转换为m进制数，即可吧
To 25:
题目中的正整数一词十分重要。
对呀，我的疑问是”正整数”这个条件就和另外的N-2个独立方程等价？
还是算法有什么巧合的地方？
这。。是我们普特南训练的一题。。
21楼, 你说的”0.10100……01……” 也许有点意思, 能具体讲一下方法么?
直接倒下！
to29,没细想，只是直觉，也许会有不可克服的错误……
比如取输入的数字可能可以为a=∑10^（-（10^k）） 上式中前m项和记作am
那么对于一个给定的n次多项式Pn(x)=anx^n+……+a1x+a0
输出结果小数的前10^10^（m+1）-A位=P(am),因为给定Pn,其导函数P'(x)在a的一个领域内肯定存在上界M，那么根据中值定理可以很容易给出A一个估计
0<P(a)-P(am)<M*(a-am)<2M*10^(-(10^m+1)) 那么A10^10^m对所有m成立
所以在考虑10^10^m到10^10^(m+1)-A位之内的数字时，我们就能只考虑P(am)
m十分大时10^(n*10^m)位前的一串数字只取决于an的数值，因为m十分大的时候其余项的和应该能够通过二项式定理给出一个估计，这个随m增长速度应该比10^10^m慢
当n不知道的时候
对所有n考察10^(n*10^m)位上的数字，m历遍正整数，对足够大m会重复出现的数字记录下来，n历遍正整数只会出现有限个非零这样的数字，当中n最大的那个就是Pn最高次系数an,之后就可以取Pn(a)-an*a^n化到n-1次的情形重复以上手段即可。
好吧，我已经被自己绕昏了，估计会有一大堆问题，不想去纠结了
正整数的话大于S都行，31楼说的却是不懂。。。
用地毯同地下室的方法整理一下:
先輸入1,得出所有系數的總和S
因為所有系數為正整數,所以所有系數必定少於S
之後輸入S,以後用以後方法取出系數C[k](k為次數)
設C[k]為系數陣列,k為次數
設darkbox(x)為黑盒函數,傳回黑盒的值p(x)
%為mod operator
vector C;
int b = darkbox(1);
int s = darkbox(b);
while(s!=0){
C.push_back(s%b);
s=(int) s/b;
}
最後得出系數的陣列
正整数隐含了系数Pn=f(N)%S^(n+1)这些方程？
呵呵 真聪明博主！
哈，5分钟就解出来了，看来我的大脑还没有退化啊。
分析：
如果系数都不超过1位数，那么取x=10，就可以知道所有系数
如果系数都不超过2位数，那么取x=100，就可以知道所有系数
…….
如果系数都不超过k位数，那么取x=10^k，就可以知道所有系数
那么我怎么知道这个k呢？哈，取x=1，就得到了所有系数之和S，所有的系数都不大于S，再将S取对数加1，就可以了啊！
综上所述：
第一步 取x=1，得到所有系数之和 S
第二部，取x=10^k，k=[log10(S)+1]，得到所有系数，其中[]表示取整，log10(x)表示以10为底的对数函数。
r=p(1)
s=p(r+1)
先输入1得到各项系数的和，能够估计每项系数的最大值不超过a,然后取a的十进位位数为n，输入10^n，这样常数项系数就被放在了第n位到第1为，x项系数就被放在了结果2n到n+1位，。。。第m项系数就被放到了mn+1到(m+1)n位，自然数的表达能力是很强的
应该是N个吧
多一分心力去注意别人，就少一分心力反省自己。