【寒假作业】【NOIP2014】解方程

首先呢。。暴力枚举是有30分的

再写个高精度你就可以得到50分的高分

那么怎么上70分和100分呢

首先如果

$$a_0+a_1x+a_2x^2+…+a_nx^n\equiv0\pmod k$$

那么会有

$$a_0\bmod k+(a_1\bmod k)x+(a_2\bmod k)x^2+…+(a_n\bmod k)x^n\equiv0\pmod k$$

不过为了防止运气差碰上了。。要多选几个素数k,全部满足才可以

这样似乎就有70分了 还不用写高精

然后我们还可以发现一个问题

我们已经得到了

$$a_0\bmod k+(a_1\bmod k)x+(a_2\bmod k)x^2+…+(a_n\bmod k)x^n\equiv0\pmod k$$

那么下式同样成立

$$a_0\bmod k+(a_1\bmod k)(x-k)+(a_2\bmod k)(x-k)^2+…+(a_n\bmod k)(x-k)^n\equiv0\pmod k$$

因为展开之后带k的项都可以约掉。。

所以我们只要判断小于k的x是否满足,大的就不用判断了。。

【所以说k别取太大了

说点什么

您将是第一位评论人!

提醒
wpDiscuz