YZOJ 一道基础题の杂谈

题目大意：给出一元二次方程的三个系数，然后求解之。

分析：题目并不是很难，而且其本意是要求运用给出的求根公式，即

 

 

，用O(1)的复杂度求出答案。作为一道入门级别的题目，它甚至都没资格上luogu的红题。按照题意，标程如下：

 

 

可是，作为优秀的盐中学子，YZOI的希望，我们怎能止步于此？【doge】

继续深挖，题目还可以这样出：

NOIP-2001-T1

 

 

这一题该怎么用上一题的做法呢？幂次升高了，求根公式似乎不管用了。但其实如果你学习过高等数学的话，还是可以用刚才的做法，如下：

盛金公式：

 

 

 

 

鉴于YZOJ的编写者数学水平有限，所以我们不考虑复数根。由此可以得出下面的程序：

 

 

 

以上是用求根公式的O（1）做法。程序固然快，可不是所有的中学生都知道卡尔丹公式或盛金公式的（这是NOIP2001年的提高T1）。所以我们开始考虑用正常的算法来解这道题。

 

我们知道，方程的根，在坐标系内对应着该方程确定的函数F（x）的零点。所以我们可以采用分治的思想去做这道题。基本的算法流程是，在题目所给的区间范围内遍历，对于每一个i进行（i,i+1.0）的Binary_Search。符合F（i）=0时，输出，到三个提前结束程序。标程如下：

 

 

 

这也是当年官方认可的正解。用到了介值定理（必修一有学过）。

 

可问题还没结束，二分是正解，但我们能不能再快一点？当然可以。先上代码：

 

 

 

 

 

 

 

 

 

用到了我们小学二年级就学过的牛顿法求函数零点。牛顿法是什么呢？上过小学二年级的自行跳过（别告诉我你二年级没学过微积分）：

这是一个可爱的函数图像：

 

估算一下在大概在零点右边的点，任取一个x0，做该曲线的切线。不难得出切线方程为：

 

 

，将你找的x0代入，可以画出图像方便理解：

 

 

我选取的这条直线l与x轴的交点为（2,0），以2为新的x0，不断进行迭代。

 

第二次迭代效果：

 

 

第二次的迭代所得切线与x轴交点已经更加接近函数的零点了。这样的工作大概做五到六次后，对于一般曲率不怎么大的函数曲线，可以得到十分精确的结果。（微积分大法好）三次函数至多三个零点，程序进行很少次数的运算就可以得到有效答案。

这是一元三次方程的，一元二次，甚至到一元n次，都可以套用，这是比求根公式，分治法强大的地方。2-3代码由luogu用户GGN_2015提供。

当然如果你是暴力主义者，可以把我码的一千多字当放屁。这题暴力竟然可以过。

 

 

 

 

码到快晕倒了，记得关注我的luogu账号，LeoWayyyyy蓝名蒟蒻。博客我会持续更新的，包括最近在学的看不懂的图论。