首页 > 代码库 > NOIP2014解方程

NOIP2014解方程

题目:求一个n次整系数方程在1-m内的整数解  n<=100 系数<=10000位 m<=100W

题解:最暴力的想法是枚举x,带入求值看是否为0.

          这样涉及到高精度乘高精度,高精度乘单精度,高精度加高精度和高精度减高精度。

          复杂度 n*m*len*len ,显然只能过30%的数据

          让我们考虑优化:

          我们先来研究一下这个算法的主要耗时在哪里

          1)将x带入方程左边求值

          2)选择多少x带入

         我们考虑第一个优化

          1)秦九韶算法

          只要我们把原方程左边化为 ((An*x+An-1)*x+An-2)*x+An-3+.....A0

          我们发现这样就不用写高精乘高精了。复杂度下降一个len 大概可以得到50分

        第二个优化

         2)去除冗余

          我们发现直接代值是复杂度相当高的,即使用了秦九韶算法复杂度也是 n*len,1s的时限仅供我们尝试100个x是否为该方程的解。

          让我们先筛去显然不可能是方程的解的数。

          我们发现0的一个特征就是模任何一个数都是0,但我们多模几个质数是否能一定保证该数为0呢?当然不行。

          那模谁呢?x。

          显然,左边 mod x=A0 mod x ,所以A0 mod x=0

          也就是说x一定是A0的约数!  (搞数竞的应该看题就想到了吧233)

          然后我们的算法来了:

          枚举1-m的每个数i,先判断它是不是A0的约数,这只要类似于高精除单精扫一遍就行了,如果不是,那么显然 2*i,3*i,……都不会是A0的约数,我们类似筛法筛掉这些

          如果是的话,带入求值判断是否为0.

          当然如果A0=0的话,该方程的一个解是0,然后其余的解都满足 A1+A2*x^1+A3*x^2+……An*x^n-1=0,我们试A1即可。

当然,到这里,算法的复杂度还是不好估计,不过是不可能达到n*m*len的上界的,应该有很大一部分被剪掉了。

如果还需要优化的话,压4位是个不错的选择。

当然,我在考场上并没有想到第二个优化。但我确实想到了mod x,但忽略了 A0这一项,认为显然左边 mod x=0,然后。。。这也是本次noip最大的一个遗憾吧。

当然,上述只是我考后的一个想法,能不能拿到满分我也不清楚。

如果神犇们发现还有什么可以优化的方法或者其它更好的方法,请指出,谢谢。

 UPD:TAT 为何看到有人说只模一个质数就能100了。。。我是sb?想了这么多。。。知道真相的我眼泪掉下来。。。

NOIP2014解方程