P4598 [HEOI2012] Akai 的数学作业 题解

给定一元 $n$ 次方程的 $n+1$ 个系数，求他的所有有理数解。

感觉这道题难度到不了紫。

首先假设 $a_0\ne0$，考虑一个方程存在有理数解 $x=\frac{p}{q}$，则对该方程因式分解，一定存在形如 $qx-p$ 的因式。又由初中所学的基础因式分解知 $q \mid a_n$，$p \mid a_0$，因此可以枚举 $a_0$ 和 $a_n$ 的因数，判断是否成立即可。

考虑 $a_0=0$，则可将原方程整体提出 $x^k$ 的因式，不要忘记在答案中加入 $0$。

时间复杂度 $O(n\sigma(a_0)\sigma(a_n))$。