插值用来求解这样一类问题：给定 $n$ 点 $(x_i,y_i)$ 求过这些点的 $n-1$ 次多项式。
设 $f(x)$ 为这个多项式，我们有：
$$
f(x)\equiv f(a)\bmod (x-a)\tag{1}
$$
这是因为：
$$
f(x)-f(a)=(a_0-a_0)+a_1(x-a)+a_2(x^2-a^2)+…
$$
而后者显然有一个根为 $a$ ，所以 $(1)$ 式得证。
通过把这 $n$ 个点代入我们可以得到：
$$
\begin{cases}
f(x)\equiv y_1\bmod x-x_1\
…\
f(x)\equiv y_n\bmod x-x_n
\end{cases}
$$
显然模数互质，所以我们考虑用中国剩余定理来解决这个事情。
令 $M=\prod_{i=1}^n(x-x_i)$ ，$m_i=\frac{M}{x-x_i}=\prod_{i\not= j}(x-x_j)$ 。并且在模 $x-x_i$ 的意义下，我们有：
$$
m_i^{-1}=\frac{1}{\prod\limits_{i\not=j}(x_i-x_j)}
$$
这是因为我们有：
$$
\prod_{i\not =j}(x-x_j)\equiv \prod_{i\not =j}(x-x_j-x+x_i)=\prod_{i\not =j}(x_i-x_j)
$$
所以我们有：
$$
f(x)\equiv \sum\limits_{i=1}^ny_im_im_i^{-1}\equiv \sum\limits_{i=1}^ny_i\prod\limits_{j\not=i}\frac{x-x_j}{x_i-x_j}
$$
这个东西可以在 $O(n^2)$ 的时间内求出。