AC. 梦想

frank_c1

[NOIP 2014] 解方程

发布于2016年05月12日 | 暂无评论 | 935阅读 | 数论

题目描述

已知多项式方程:

a_0+a_1x+a_2x^2+...+a_nx^n=0

求这个方程在[1,m]内的整数解(nm均为正整数)。

输入格式

第一行包含2个整数n,m,每两个整数之间用一个空格隔开。

接下来的n+1行每行包含一个整数,依次为a_0,a_1,a_2,...,a_n

0 \lt n \le 100,|a_i| \le 10^{10000},a_n \neq 0,m \le 1000000

输出格式

第一行输出方程在[1,m]内的整数解的个数。

接下来每行一个整数,按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。

题目解析

结清一些陈年老账……

我们知道一元高次方程是没有通解的,而且本题系数非常大,显然不是用数学方法求解。

我们来观察一些性质。

考虑将方程放到模意义下,假设我们对所有系数对p取模。如果在x取某一定值时,方程在模p意义下是成立的,那么x有很大几率是原方程的解。反之,如果方程在模p意义下不成立,那么在原方程中也一定不成立,x一定不是原方程的解。于是我们可以选取多个模数p,分别对[1,m]中的整数代入验证,就可以在极大的概率下排除所有错解。

若我们选取k个模数验证,总复杂度是O(knm)的,还是不够快。

我们考虑,在模p意义下,若f(x) = 0,则一定有f(x+p) = 0。反之,若f(x) \neq 0,则一定有f(x+p) \neq 0。所以我们只需验证[1,p),其余范围的整数可以由前面的结果推得。我选择的质数大概在10 ^ 4级别。这样就可以顺利通过本题了。复杂度不会分析……