cubic

Write a function P7:

• Input parameters: integers a, b, c, d satisfying $1\le\max(|$a$|,|$b$|,|$c$|,|$d$|)\le10^9$

• Return value: a list of all rational roots of the equation a$x^3+$b$x^2+$c$x+$d$=0$, in any order. (Each root should be included only once.)

  • Suppose the exact answer is $[t_0,t_1,\cdots,t_{n-1}]$ and your output is $[u_0,u_1,\cdots,u_{m-1}]$.
  • For every non-negative integer $k$, let $r(k)=\{i\in\mathbb Z:0\le i\<k\}=\{0,1,\cdots,k-1\}$.
  • Your answer is graded correct if and only if there exists a bijective function $\sigma\colon r(n)\to r(m)$ such that [\frac{|u_{\sigma(i)}-t_i|}{\max(1,|t_i|)}\le10^{-6}\qquad\text{for all }i\in r(n)]

• Hint: The rational root theorem states the following.

  • Consider a polynomial $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$ with integer coefficients where $a_n$ and $a_0$ are nonzero.
  • If $\displaystyle f\left(\frac{p}{q}\right)=0$, where $|p|$ and $|q|$ are relatively prime positive integers, then $\displaystyle\frac{a_0}{p}$ and $\displaystyle\frac{a_n}{q}$ are integers.