Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 245 D問題 Polynomial division

AtCoder ABC ABC245 D問題 400 pts

問題

提出解答

問題の概要

$N$ 次多項式 $A(X):=A_N X^N+\dots+A_0$ と $M$ 次多項式 $B(X):=B_N X^N+\dots+B_0$ がある. ここで, $A,B$ の各係数の絶対値は $100$ 以下である.

$C(X):=A(X) B(X)$ としたとき, $A,C$ が与えられるので, $B$ を求めよ.

ただし, $B$ が一意に定まるような $A,C$ が与えられる.

制約

$1 \leq N,M \lt 100$
$A$ の各係数の絶対値は $100$ 以下
$B$ は一意に存在する.

解法

高校数学 II で習う多項式の除法により, 以下のようなアルゴリズムで $B$ を求めることができる.

$B \gets 0$
の次数が以上である限り, 以下を行う.
- $C$ の最高次の係数を $\gamma$ , $A$ の最高次の係数を $\alpha$ としたとき, $B$ に $-\frac{\gamma}{\alpha} X^{\operatorname{deg}(C)-\operatorname{deg}(A)}$ を加え, $C$ から $-\frac{\gamma}{\alpha} A X^{\operatorname{deg}(C)-\operatorname{deg}(A)}$ を引く.
ここまで来た時の $B$ が商, $C$ が余り (今回の制約下では $C(X)=0$ ) である.

このアルゴリズムによって, 時間計算量を $O(NM)$ で求めることができた.