拉格朗日插值法就是构造一个多项式，使得恰好在每一个x处取到对应的y 首先，n+1个点(xi,yi)若xi不同，则可以确定唯一的最高幂次不超过n的多项式。而如果题目直接或是间接给出了n+1个点，让我们求由这些点构成的多项式在某一个位置的取值，那么应用拉格朗日插值可以在O(n2 )的时间内解决这一问题 基本内容： 思路如下： 对于这个函数，要想在k=x[i]的时候取到y[i]，并且y[i]仅在这一情况对答案有影响，就要构造出一项K[i]y[i],使得x仅在取到x[i]时K为1,其他情况K[i]为0。 于是，仿照中国剩余定理的思路，有了如下构造方式： (1)首先，x...