24OJ #27. 【2017省选模拟】方程

这题考场上感觉身体被掏空,没啥想法。。QAQ。。看了题解好像还是没啥想法,随便写点…..

我们考虑一下。

如果b == 1。我们考虑一下,如果a,c也都是1,那么显然有无穷组解,非常显然,可以任意一位的系数为1.其余的为0.

然后我们考虑一下,b > 1。我们考虑从a,b,c这三个值中能得到什么额外的条件。

我们考虑一下,条件无非就是

f(a) = b

a ^ n * xn + a ^ (n – 1) ^ x(n – 1) ……a ^ 2 * x2 + a ^ 1 * x1 + x0

f(b) = c

b ^ n * xn + b ^ (n – 1) ^ x(n – 1) ……b ^ 2 * x2 + b ^ 1 * x1 + x0

然后我们可以发现点奇妙的事情,如果我们对于第一个式子取膜a,显然最后左面只剩x0。

我们对第二个式子取膜b,显然最后左面也只剩x0。如果两个式子得到的值相同,显然证明我们确定了一个系数。我们可以将x0减去然后除去一个a去递归进行。

考虑一下边界,如果最后都是0了,显然已经完美的验证是成立的了。没有出现偏差,我们认为出现了一个方案。如果最后一个为0,一个不为0,也完美的证明了我们这组解出现了问题,不能算入总数,并且应当停止,因为已经为0.无法继续递归了。

上面的话大概讲一个感觉,然后我们考虑一些细节问题,如果一个式子取膜后等于0,有两种可能,要么这个x0 为 0。要么这个x0 为 取膜的值。怎么分辨呢,我们考虑如果另外一个式子取膜也等于0,那么显然x0为0,然后递归解决。如果找到一组可行解,x==y就不需要

发表评论