因数分解（多項式の除算）

AtCoder

D - Polynomial division

https://atcoder.jp/contests/abc245/tasks/abc245_d

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

#include <iostream>
#include <vector>

int main() {
    int N, M;
    std::cin >> N >> M;
    N++; M++;
    int C_degree = (N + M - 1);
    std::vector<int> A(N), B(M, 0), C(C_degree), CC(C_degree, 0);
    for (int n = 0; n < N; n++) std::cin >> A[n];
    for (int nm = 0; nm < C_degree; nm++) std::cin >> C[nm];

    //for (int n = 0; n < N; n++) {
    //  for (int m = 0; m < M; m++) {
    //      CC[n + m] += (A[n] * B[m]);
    //  }
    //}

    //B[M - 1] = (C[C_degree - 1] / A[N - 1]);
    //B[0] = (C[0] / A[0]);

    for (int m = (M - 1); 0 <= m; m--) {
        int tmp_cor = (C[(N - 1) + m] / A[(N - 1)]);
        B[m] = tmp_cor;
        for (int n = (N - 1); 0 <= n; n--) {
            C[m + n] -= (B[m] * A[n]);
        }
    }

    for (int m = 0; m < M; m++) std::cout << B[m] << " ";
    std::cout << std::endl;
}