AdditionalFile178.zip

#178. 多项式求根

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB 通过: 46 | 提交: 87

题目描述

这是一道模板题。

给定一个多项式方程 $\sum_{i=0}^{n} a_i x^i = 0$，求出它在模素数 $p$ 意义下的所有根。

输入格式

第一行两个正整数 $n, p$，表示多项式的次数和模数。

第二行 $n+1$ 个整数 $a_0, a_1, \cdots, a_n$，表示这个多项式。

输出格式

第一行一个整数 $k$，表示方程根的个数。

第二行 $k$ 个从小到大的整数，表示所有根。注意，这里我们认为重根只算一个。

样例 1

输入

2 5
1 0 1

输出

2
2 3

样例 2

输入

2 7
1 0 1

输出

0

数据范围与提示

$3 \le p \le 10^9, 1 \le n \le 100, 0 \le a_i < p, a_n \neq 0$。