有关整系数多项式化简的一个问题

sunwukong

已知，正整数数列 \(A_0, A_1, \dots, A_n\)，这个数列的最大公约数为\(1\)
求最大的正整数 \(p\) 和 最大的正整数 \(q\)，满足
\[\frac{A_0}{q^n},\frac{A_1}{q^{n-1}},\ldots,\frac{A_{n-1}}{q}, \quad \frac{A_n}{p^n},\frac{A_{n-1}}{p^{n-1}},\ldots,\frac{A_1}{p}\]
都是整数。

题目背景：
已知：\[f(x)=A_0+A_1\*x+\dots+A_n\*x^n\]
如果：\[\begin{split}A_0&=a_0\*q^n\\A_1&=a_1\*p\*q^{n-1}\\ &\cdots \\ A_{n-1}&=a_1\*p^{n-1}\*q\\ A_n&=a_n\*p^n\end{split}\]
则设：\[y=\frac{p\*x}{q}\]
那么：\[F(y)=f(x)=q^n\*(a_0+a_1\*y+\dots+a_n\*y^n)\]

请问有高效的算法么？

mathe

其实就是两个相同算法问题分别算p和q.
比如算p,我们知道它是(A_1,A_2,…,A_n)的因子，同样其平方为(A_2,A_3,…,A_n)的因子等
这个问题还要看整数的规模，如果都不是太大，直接因子分解(A_1,A_2,…,A_n)然后分别计算各素因子允许的最大次数即可