拉格朗日插值

显然， \(f(x)\equiv f(a) \pmod {(x-a)}\)

则对于已知 \(f(x_0),f(x_1), f(x_2), f(x_3),\cdots,f(x_n)\) ，有

\[\begin{cases} f(x)\equiv x_0 \pmod {(x-x_0)}\\ f(x)\equiv x_1 \pmod {(x-x_1)}\\ \cdots\\ f(x)\equiv x_n \pmod {(x-x_n)} \end{cases} \]

则显然 \(f(x)=\sum_{i=1}^{n}{y_im_im_i^{-1}}=\sum_{i=1}^n{y_i}\prod_{j\ne i}{\frac{x-x_j}{x_i-x_j}}\)