cubic

다음 함수 P7 을 작성하시오.

• 입력 매개변수: $1\le\max(|$a$|,|$b$|,|$c$|,|$d$|)\le10^9$ 를 만족하는 정수 a, b, c, d

• 반환값: 방정식 a$x^3+$b$x^2+$c$x+$d$=0$ 의 모든 유리근을 임의의 순서로 담은 리스트 (각 근은 한 번만 포함한다.)

  • 정답이 $[t_0,t_1,\cdots,t_{n-1}]$ 이고 출력이 $[u_0,u_1,\cdots,u_{m-1}]$ 이라고 하자.
  • 음이 아닌 정수 $k$ 에 대해 $r(k)=\{i\in\mathbb Z:0\le i\<k\}=\{0,1,\cdots,k-1\}$ 로 정의한다.
  • 전단사 함수 $\sigma\colon r(n)\to r(m)$ 가 존재하여 모든 $i\in r(n)$ 에 대해 [\frac{|u_{\sigma(i)}-t_i|}{\max(1,|t_i|)}\le10^{-6}] 이면 정답으로 인정된다.

• 힌트: 유리근 정리는 다음과 같다.

  • $a_n$ 과 $a_0$ 이 0이 아닌 정수 계수 다항식 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$ 를 생각하자.
  • $|p|$ 와 $|q|$ 가 서로소인 양의 정수이고 $\displaystyle f\left(\frac{p}{q}\right)=0$ 이면 $\displaystyle\frac{a_0}{p}$ 와 $\displaystyle\frac{a_n}{q}$ 는 정수이다.