首页 > 代码库 > 2742: [HEOI2012]Akai的数学作业
2742: [HEOI2012]Akai的数学作业
Description
这里是广袤无垠的宇宙这里是一泻千里的银河
这里是独一无二的太阳系
这里是蔚蓝色的地球
这里，就是这里，是富饶的中国大陆！
这里是神奇的河北大地
这里是美丽的唐山
这里是神话般的唐山一中
这里是Akai曾经的教室
黑板上还留有当年Akai做过的数学作业，其实也并不是什么很困难的题目:
“
给出一个一元n次方程：
a0 + a1x + a 2 x2 +…+ anxn= 0
求此方程的所有有理数解。
” Akai至今还深刻记得当年熬夜奋战求解的时光
他甚至还能记得浪费了多少草稿纸
但是却怎么也想不起来最后的答案是多少了
你能帮助他么？
Input
第一行一个整数n。第二行n+1个整数，分别代表a 0 到a n
Output
第一行输出一个整数t，表示有理数解的个数
接下来t行，每行表示一个解
解以分数的形式输出，要求分子和分母互质，且分母必须是正整数特殊的，如果这个解是一个整数，那么直接把这个数输出
等价的解只需要输出一次
所有解按照从小到大的顺序输出
Sample Input
3
-24 14 29 6
-24 14 29 6
Sample Output
3
-4
-3/2
2/3
-4
-3/2
2/3
HINT
【数据范围】
对于30%的数据，n<=10
对于100%的数据，n <= 100，|a i| <= 2*10^7，an≠ 0
Mogical Mathematics
好像是求$f(x) = a_0 + a_1x + a_2x^2 + … + a_nx^n$ 的零点
我们可以发现（有理数域下）式子一定可以变成 $g(x) * \Pi(b_ix + c_i)$
所以根就是$-\frac{c_i}{b_i}$
然后听说今天早上CMO大爷给我们证了一下$c_i$一定是$a_0$因数，$b_i$一定是$a_n$因数，具体是这样的：式子其实在复数域下是$\Pi(b_ix + c_i)$，然后所有$b_i$的积就是$x_n$的系数($a_n$)，所有$c_i$的积就是常数项的系数($a_0$)
然后，我们就可以求出$a_n$、$a_0$所有因数，然后大力check一下就好啦。具体怎么check呢，就是代回去算23333（模意义下）
然后我就滚去写代码了QAQ
2742: [HEOI2012]Akai的数学作业
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。