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))。

code

一些注意事项