問題文を言い換えると、\(\frac{C(x)}{A(x)}\) を求めればよく、 多項式の除算に乗っ取って、\(B(x)\) について次数の大きいものから順に決定していけばよいです。

より形式的には次のように解くことができます。 以下、より一般に \(B(x)\) の \(k\) 次の係数を \(B_k\) とおきます。 \(k>M\) に対して, \(B_k=0\) です。 このとき、\(A(x)\) が \(N\) 次式であることに注意すると、 \(C(x)=A(x)B(x)\) の両辺の係数を比較することで次の関係が成り立ちます。

• \(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}\)
  \(\vdots\)
• \(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\)

よって、\(i=0,1,\ldots, M\)について、\(k> M-i\) において\(B_k\) の値が定まっていた時、

\[ 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} \]

として \(B_{M-i}\) の値を求めることができます。 \(i=0\) のとき \(k> M\) で\(B_k=0\) であり、\(i=i_0\) \((i_0>0)\) のときについて、\(i<i_0\) のときの結果を用いて帰納的に \(B_{M-{i_0}}\) の値を求めることができます。

このとき計算量は \(O(NM)\) で十分高速であり、また \(32\) ビット整数型で管理してオーバーフローすることもありません。よってこの問題を解くことができました。

#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;
}