多项式是由一组常数系数，a、b、c、……（数值）确定的。 

多项式求解问题就是找到一个值 x，使这些项的总和等于 0. 根据 x 的最高次数分别称为线性、二次、三次、四次、五次、六次、七次、八次...... 多项式。我们称 y = a x + b 为线性，是因为它的图线是一条直线. 比如令 a = 2，b = 3，

这样的表达式被称为不尽根式. 最常见的应用是在几何上. 圆、抛物线和双曲线通常由二次多项式指定。当我们想知道一个二次多项式与已知直线何时相交时，我们就得到一个二次方程. 这甚至发生在 双曲线是矩形的，例如：

表示双曲线的分支与直线相交的方程为

不管怎样，求解二次方程：

我们可以把这些值作为绘图范围

该图形以交点作为起点和终点. （ {1, 2, 4} 是为了去除额外的 x.）

要是双曲线是颠倒的，貌似就没解了：

也就是说，解含有虚数. 二次方程是通过配方法来求解的，两边同时加上b^2/4a-c:

然后左边配成平方除以4a：

我们可以取两边的平方根.

正如"每个人"都记着二次方程的解，"没有人"记得三次方程的解。原因是：

现在考虑一个简单情形：

这么复杂的式子怎么会是实数呢？让我们看一下虚部：

那好吧，老天爷，告诉我们实部是啥吧！

三角函数？！还不如平方根和立方根呢！

天啊！那些三角函数是实数，但为啥这里却跟着一堆虚数单位？- 1.1、.35 和 .75 在哪呢？？请给出数来.

它们就在那，但这些 0. i 是怎么回事？奇怪的是，它们是不可避免的. 作为一个数学分支的伽罗瓦理论已经证明，不含虚数立方根的解式是不存在的，即使它们的加和为实数.

Henry Baker 的动画（本文顶部可以看到实际动画）展示了均为实数的三个根之间的关系：

这是张一般情况下的图片——三个实根的三次方程有一个拐点，它们关于拐点对称. 如果将拐点平移到原点，则会得到一个奇函数  f（-x ）= -f（x）.

四次方程可以通过将两条曲线相交得到. 一般情况下的四次方程会让人有点抓狂，如果不怕的话就按住 shift return 键试试吧.

求解五次方程就更是不要命了.

哈哈，Mathematica 放了我们一马，结果被剪切了，但为什么不至少提供一下互动大型表达式浏览器呢？因为它不能. 不存在一般五次方程的根表达式. 显然，通过因式分解我们可以求解某些五次方程.

历经几个世纪的挫败，求解五次方程已经与三等分角和倍立方问题一样成为困扰人们的几大数学难题。

许多人错误地认为唯一可解的五次方程要么是可因式分解的，要么是显而易见的，如（x + a）^ 5 + b = 0. 但只有一小部分，接近0％，可以巧妙地解决，比如：

它的根相当繁琐. 唯一的实根是

至少从外观看来是实数. 平凡的 Mathematica 无法求解——连验证都不行！只能近似：

我曾经（正确地？）说服自己，每个可求解的六次方程都可以降次到具有二次不尽根系数的三次方程或具有三次不尽根系数的二次方程. 但谁会想要求解这样一个方程呢？几何再次派上用场了. 问题：将一个正方形拆分成有限个锐角、等腰三角形. 可以用十个：

不能进行因式分解. 然而

可以求得所有六个解！怎么实现呢？这个六次方程可以写作

也就是说，将三次方程替换为二次方程。如果我们注意到这一点，我们只是用y来代替 x ^ 3 - x ^ 2 - 2 ，对得到的二次方程求 y，然后求解关于 x 的三次方程，用 y 表示。我们是怎么注意到这一点的？用魔法函数

这正好是 Solve 函数所了解的. 知道吗？你的八次方程可能只是三个二次方程的组合.

但请注意：这个六次方程的解，既不能因式分解

所以括号中的数量满足最小次数为36的最小多项式！

令人惊奇的是，这是一个甚至连 Mathematica 第11版都不知道的诀窍：如果系数形成回文，六次甚至八次方程总是可以求解！例如，

（失败。）但是我们可以对付完全一般的情况！对于任意a，b，c，d，假设 x 满足互反多项式（所以被称作回文式）

现在假设 y = x + 1/x （或写作 x y = x^2 + 1），求六次多项式除以这个二次多项式（关于 x）的余式：

求这个余式意味着减去二次式的倍数，使得六次多项式将简化为关于 x 的线性多项式. 但是我们假定了二次和六次多项式都是0，所以我们从0减去0，得到x和y之间的可疑关系， 乘以我们可以求解的 y 的三次式！通过 y = x + 1 / x 来求解x.

回文多项式被称作互逆多项式的原因是，如果用 1/x 代替 x，两者具有相同的根，从而将系数的次序逆转（并除以 x^6）.

这个令 y = x + 1/x 的技巧可以成功的关键是我们可以将各项用它们的倒数匹配，并利用关系：

朱利安和我有一个七次方程求解程序，但他不相信它能找到所有的解. 超过七次以后，能找到一个强有力的求解器机会会大大减小，TA在理论上可以求解的概率也是如此. 但是如果你的问题不是随机组成的，那么总是值得一试.

由于作者是一个初二蒟蒻，有一些地方可能存在问题，请多指教。喷轻点
你以为我会先讲插值吗？

所有数列都有规律——拉格朗日

先 $orz$ 拉格朗日一下：

约瑟夫·拉格朗日（Joseph-Louis Lagrange，）全名为约瑟夫·路易斯·拉格朗日，法国著名数学家、物理学家。1736年1月25日生于意大利都灵，1813年4月10日卒于巴黎。他在数学、力学和天文学三个学科领域中都有历史性的贡献，其中尤以数学方面的成就最为突出。
拉格朗日总结了18世纪的数学成果，同时又为19世纪的数学研究开辟了道路，堪称法国最杰出的数学大师。同时，他的关于月球运动（三体问题）、行星运动、轨道计算、两个不动中心问题、流体力学等方面的成果，在使天文学力学化、力学分析化上，也起到了历史性的作用，促进了力学和天体力学的进一步发展，成为这些领域的开创性或奠基性研究。

然后让我们想想为什么慢？因为我们知道的太多了。
我们发现求出 $f(x)$ 的部分好像是多余的，考虑直接求出 $f(k)$。
乍一看好像十分懵逼，我们一点一点地分析它。
首先显然 $L_n(x)$ 是一个 $n$ 次的多项式，然后再让我们分析一下 $\ell_i(x)$，我们可以发现它有一些神奇的性质：

所以每加入一个点，我们用 $O(n)$ 的时间复杂度计算出重心权 $w_i$，即可求出新的 $L_n(x)$。

于是就可以进行加入、撤销的操作了，它有向后稳定性。

这就是重心拉格朗日插值法（第二型）或是叫做真正的重心拉格朗日插值公式。它比重心拉格朗日插值法（第一型）更好计算，常数更小，向前稳定，并且勒贝格常数很小，用 $x_i=\cos(\frac{(2i+1)\pi}{2(n+1)})$ 就是切比雪夫插值节点插值效果好，可以很好地模拟给定的函数，使得插值点个数趋于无穷时，最大偏差趋于零。

艾萨克·牛顿（1643年1月4日—1727年3月31日）爵士，英国皇家学会会长，英国著名的物理学家，百科全书式的“全才”，著有《自然哲学的数学原理》、《光学》。

他在1687年发表的论文《自然定律》里，对万有引力和三大运动定律进行了描述。这些描述奠定了此后三个世纪里物理世界的科学观点，并成为了现代工程学的基础。
他通过论证开普勒行星运动定律与他的引力理论间的一致性，展示了地面物体与天体的运动都遵循着相同的自然定律；为太阳中心说提供了强有力的理论支持，并推动了科学革命。

在力学上，牛顿阐明了动量和角动量守恒的原理，提出牛顿运动定律。

在光学上，他发明了反射望远镜，并基于对三棱镜将白光发散成可见光谱的观察，发展出了颜色理论。他还系统地表述了冷却定律，并研究了音速。

在数学上，牛顿与戈特弗里德·威廉·莱布尼茨分享了发展出微积分学的荣誉。他也证明了广义二项式定理，提出了“牛顿法”以趋近函数的零点，并为幂级数的研究做出了贡献。

在经济学上，牛顿提出金本位制度。

然后我们定义差商（均差）的概念：即导数的近似值，对等步长的离散函数 $f(x)$ ，其 $n$ 阶差商就是它的 $n$ 阶差分与其步长的 $n$ 次幂的比值。 ——摘自

我们考虑存在未知点 $x$ 的差商，移项可得

取哪一个都会是 $0$，可以去掉。
实现的时候便可以增量构造，我们时刻维护 $x_n$ 结尾的 $n$ 个差商和多项式 $\prod(x-x_i)$ 即可，差商用定义的公式递推，多项式因为每次乘二项式，直接递推，两个东西都可以 $O(n)$ 维护。总复杂度为 $O(n^2)$。
不过它比拉格朗日插值更好的是，它可以插出多项式的系数。当给出的节点等距时，使用差分能达到更优的效果，其计算更加简便。

如果 $O(n\log^3 n)$还是满足不了大佬AKIOI的需求时，我们就继续换方法。

注意：以下内容可能引起不适，建议学过的同学学习。

【高能预警】下面的公式非常密集！！！

递归求解即可，时间复杂度 $O(n\log^2n)$，常数极大。

不过代码就不给了，因为我还没写出来

不过其实我们日常生活不会用到IOI不考，所以实用性不强，但是它可以解决一些毒瘤的问题。

1/(1+z)当z的模小于1时，可以展开成泰勒级数，当把z换成1/z，此时z的模大于1，也就是1/z的模小于1，这样 1/(1+1/z)同样可以展开成泰勒级数，但有一条，0<1/z的模<1，注意这里1/z的模不可能为0，是大于零，可见1/z在零处无定义，为什么还是可以展开成麦克劳林级数？麦克劳林级数是在0点处展开的泰勒级数，所以这个不能照搬吧，不知道为什么直接照搬？ 因为我是这样想的，泰勒级数展开是在圆盘上的圆心处，圆心是由定义的，即在圆心处也解析，这