BoB004-G: Quadratic Equation

2 secs 1024 MB
kyaneko999's icon kyaneko999

解説

22 次方程式の解の公式を用いれば x=A±A24B2x=\displaystyle\frac{A\pm\sqrt{A^2-4B}}{2} と解が求められますが,小数型で扱うため誤差が生じる恐れがあります.
代わりに解と係数の関係を用います.方程式の解を x=α,βx=\alpha,\beta とすると以下が成り立ちます.

  • α+β=A\alpha+\beta=A
  • αβ=B\alpha\beta=B

22 つ目の式については,BB22 つの正の約数の積で表しているため,候補となる α,β\alpha,\beta を素因数分解や約数列挙などを用いて求めることができます.
よって,BB の約数 pp を全探索し,p+(B/p)=Ap+(B/p)=A が成り立つものが存在するかを調べれば良いです.
計算量は BB の最大値を MM として O(M)O(\sqrt{M}) です.

解答例(Python)