D Polynomial division AtCoder Beginner Contest 245

AtCoder Beginner Contest 245

D. Polynomial division

这题是一个模拟题，模拟多项式除法的运算过程。

手动运算多项式除法的步骤如下：

把被除式、除式按某个字母作降幂排列，并把所缺的项用零补齐．用被除式的第一项除以除式第一项，得到商式的第一项．用商式的第一项去乘除式，把积写在被除式下面（同类项对齐），消去相等项，把不相等的项结合起来．把减得的差当作新的被除式，再按照上面的方法继续演算，直到余式为零或余式的次数低于除式的次数时为止,被除式=除式×商式+余式。若余式为零，说明这个多项式能被另一个多项式整除

这一题不用考虑余数问题，因为A*B=C， 必定C能整除A。

代码

#include <iostream>
#include <algorithm>
#include <set>
#define int long long
using namespace std;const int N = 2e5 + 10;
// 多项式除法
// 大除法模拟
int a[500],c[500],b[500];
signed main()
{int n, m;cin >> n >> m;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] << " ";puts("");
}