D - Polynomial division Editorial by en_translator

The Problem Statement asks to find \(\frac{C(x)}{A(x)}\). The coefficients of \(B(x)\) can be determined in the decreasing order of its degree in manner of divisions of polynomials.

Formally, the problem can be solved as follows. We generally denote the \(k\)-th coefficient of \(B(x)\) as \(B_k\). For \(k > M\), \(B_k = 0\). Since \(A(x)\) is a polynomial of degree \(N\), by comparing the coefficients of both hand sides of \(C(x)=A(x)B(x)\), we have the following relation:

  • \(C_{N+M}=A_NB_M+A_{N-1}B_{M+1}+\cdots +A_1B_{N+M-1}+A_0B_{N+M}\)
  • \(C_{N+M-1}=A_NB_{M-1}+A_{N-1}B_{M}+\cdots +A_1B_{N+M-2}+A_0B_{N+M-1}\)
  • \(C_{N+1}=A_NB_1+A_{N-1}B_2+\cdots +A_1B_N+A_0B_{N+1}\)
  • \(C_{N}=A_NB_0+A_{N-1}B_1+\cdots +A_1B_{N-1}+A_0B_N\)

Therefore, for \(i=0,1,\ldots, M\), when we have determined the values of \(B_k\) for \(k> M-i\), we can find the value of \(B_{M-i}\) as

\[ B_{M-i}=\frac{C_{N+M-i}-A_{N-1}B_{M-i+1}-A_{N-2}B_{M-i+2}\cdots -A_0B_{N+M-i}}{A_N}. \]

For \(i=0\), we have \(B_k=0\) for \(k> M\); for \(i=i_0\) \((i_0>0)\), the value of \(B_{M-{i_0}}\) can be inductively found based on the results for \(i<i_0\).

The time complexity of this solution is \(O(NM)\), which is fast enough. Moreover, it can be managed in \(32\)-bit integer type variables without overflows. Therefore, the problem has been solved.

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n, m;
	cin >> n >> m;
	vector<int>a(n + 1), b(m + 1), c(n + m + 1);
	for (int i = 0; i <= n; i++)cin >> a[i];
	for (int i = 0; i <= n + m; i++)cin >> c[i];
	for (int i = m; i >= 0; i--) {
		b[i] = c[i + n] / a[n];
		for (int j = 0; j <= n; j++)c[i + j] -= b[i] * a[j];
	for (int i = 0; i < m; i++)cout << b[i] << " ";
	cout << b[m] << endl;
	return 0;

last update: