다항식 나눗셈의 몫을 빠르게 구하는 방법

차수가 $n$인 다항식 $f(x) = c_0 + c_1x^1 + c_2x^2 + \cdots + c_nx^n (c_n \ne 0)$가 있다. 그리고 차수 $m$인 다항식 $g(x) = d_0 + d_1x^1 + d_2x^2 + \cdots + d_mx^m (d_m \ne 0)$이 있다. 이를 다항식 $q$와 $r$을 이용하여, $f(x) = g(x)q(x) + r(x)$라고 나타내 보자. $r(x)$의 차수가 $m$보다 작은 경우, $f$를 $g$로 나눈 몫을 $q$, 나머지를 $r$이라고 정의한다. 다항식 $q$의 차수는 $n-m$이다.

 

다항식의 나눗셈을 교과과정에서 배운대로 구현한다면 $O(nm)$ 시간복잡도가 된다. 이를 좀 더 빠르게 하는 방법에 대해서 알아보자.

 

$\textrm{Rev}(f)$를 다항식 $f$의 계수를 좌우로 뒤집은 것으로 정의하자. 즉, $\textrm{Rev}(f) = c_n + c_{n-1}x^1 + c_{n-2}x^2 + \cdots + c_0x^n$이다. 이는 다음과 같은 성질을 가진다.

$$\textrm{Rev}(f) = x^nf(\frac{1}{x}) \Rightarrow \textrm{Rev}(fg) = \textrm{Rev}(f)\textrm{Rev}(g)$$

$f = gq + r$이라는 식에 Rev를 씌워보면 다음과 같다.

$$\textrm{Rev}(f) = \textrm{Rev}(g)\textrm{Rev}(q) + x^{n-\deg(r)}\textrm{Rev}(r)$$

여기서, $\deg(r)$은 다항식 $r$의 차수를 의미한다. $\deg(r) < m$이므로 $n-\deg(r) \ge n-m+1$이다. 따라서 아래 식을 만족한다.

$$\textrm{Rev}(f) = \textrm{Rev}(g)\textrm{Rev}(q) \mod x^{n-m+1}$$

만약, $\textrm{Rev}(g)$의 modulo에서의 역함수 $\textrm{Rev}(g)^{-1}$이 존재한다면 다음 식을 만족한다.

$$\textrm{Rev}(q) = \textrm{Rev}(f)\textrm{Rev}(g)^{-1} \mod x^{n-m+1}$$

다항식 $q$의 차수가 $n-m$이기 때문에 $\textrm{Rev}(q) \mod x^{n-m+1}$는 $\textrm{Rev}(q)$가 되고, 이를 통해 다항식 $q$를 알 수 있다.

 

몫이 되는 다항식 $q$를 구하기 위해, $\textrm{Rev}(g)^{-1} \mod x^{n-m+1}$을 구하는 방법을 알아보자.

 

이 문제를 일반화하여, 상수 계수가 0이 아닌 다항식 $h$에 대해 $h^{-1} \textrm{ mod } x^l$을 구하는 방법을 알아보자. 다항식 $h$의 상수 계수를 $t$라고 한다면, $l = 1$일 때 $h^{-1} = \frac{1}{t} \textrm{ mod } x$가 된다. 이제 $h^{-1} \textrm{ mod } x^l$을 알고 있을 때, $h^{-1} \textrm{ mod } x^{2l}$을 구하는 귀납적인 방법으로 $l = 2^k$ 꼴일 때 $h^{-1} \textrm{ mod } x^l$을 구할 것이다.

 

$ah = 1 \textrm{ mod } x^l$인 다항식 $a$가 있다. 우리가 구하고 싶은 것은 $\tilde{a}h = 1 \textrm{ mod } x^{2l}$인 $\tilde{a}$이다. $\tilde{a} = a + bx^l$를 만족하는 다항식 $b$가 존재한다. 또한, $h = h_0 + h_1x^l$라고 표현할 수 있다. 여기서 다항식 $a$와 다항식 $h_0$의 차수는 $l$ 미만이다.

$$\tilde{a}h = (a+bx^l)(h_0+h_1x^l) = ah_0 + (bh_0 + ah_1)x^l = 1 \mod x^{2l}$$

$ah_0 = 1 + cx^l \textrm{ mod } x^{2l}$으로 나타낼 수 있다. 이것을 위 식에 대입하면 다음과 같다.

$$\tilde{a}h = 1 + (c+bh_0+ah_1)x^l = 1 \mod x^{2l}$$

이때, $c+bh_0+ah_1 = 0 \textrm{ mod } x^{2l}$이 됨을 알 수 있다. 이를 $b$에 대한 식으로 표현하면 다음과 같다.

$$b = -h_0^{-1}(ah_1+c) = -a(ah_1+c) \mod x^{2l}$$

이를 $\tilde{a} = a+bx^l$에 대입하면 다음과 같다.

$$\tilde{a} = a + (-a^2h_1-ac)x^l \\= a \left[ 1-cx^l-ah_1x^l \right] \\= a \left[ 2 - a(h_0+h_1x^l) \right] \\= a \left[ 2 - ah \right] \mod x^{2l}$$

 

즉, 2번의 다항식 곱셈과 1번의 다항식 덧셈을 하면 $l$이 2배 증가한다. $l \ge n-m+1$이 될 때까지 반복하여 $\textrm{Rev}(g)^{-1}$을 구하고, 이를 $\textrm{Rev}(f)$에 곱하면 $\textrm{Rev}(q)$를 구할 수 있다. 이제 다항식 계수의 순서만 좌우로 다시 뒤집으면 구하고자 하는 몫이 되는 다항식 $q$를 구할 수 있다.

 

다항식의 곱은 FFT를 이용하여 $O(n \lg n)$ 시간복잡도에 수행할 수 있다. 곱하는 다항식의 차수는 처음 1에서 시작하여 두 배씩 증가하고 $n-m+1$과 같거나 커질 때까지 진행된다. 전체 시간복잡도를 계산해보면 다음과 같다.

$$O(1 \lg 1 + 2 \lg 2 + 4 \lg 4 + \cdots + n \lg n) \le k(1+2+4+\cdots+n) \lg n \le 2k n \lg n = O(n \lg n)$$

 

이 방법은 특정한 조건 안에서 키타마사법과 NTT를 섞어 사용하여 선형점화식을 가지는 수열의 $N$ 번째 항을 $O(k \lg k \lg N)$ 시간안에 구할 때 유용하게 사용된다. 관련 글을 참고하자.