Skip to content

L2-018 多项式A除以B

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。

输入格式

输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：

N e[1] c[1] ... e[N] c[N]

其中N是该多项式非零项的个数，e[i]是第i个非零项的指数，c[i]是第i个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。

输出格式

分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后1位。同行数字间以1个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为0 0 0.0。但非零多项式不能输出零系数（包括舍入后为0.0）的项。在样例中，余多项式其实有常数项-1/27，但因其舍入后为0.0，故不输出。

输入样例 

4 4 1 2 -3 1 -1 0 -1
3 2 3 1 -2 0 1

输出样例 

3 2 0.3 1 0.2 0 -1.0
1 1 -3.1

Solution

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

#define db double
#define ll long long
#define INF 0x3f3f3f3f
#define N 100010
#define pid pair<int, db>
#define fi first
#define se second
const db eps = 0.05;
int n, m;
db A[N], B[N];
db Q[N];

void out(db *a) {
    vector<pid> vec;
    for (int i = 3000; i >= 0; --i)
        if (abs(a[i] - 0) > eps)
            vec.push_back(pid(i, a[i]));
    if (vec.empty())
        puts("0 0 0.0");
    else {
        int len = vec.size();
        printf("%d", len);
        for (int i = 0; i < len; ++i) printf(" %d %.1f", vec[i].fi, vec[i].se);
        puts("");
    }
}

int main() {
    //	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    scanf("%d", &n);
    int a = 0, b = 0;
    for (int i = 1, e, c; i <= n; ++i) {
        scanf("%d%d", &e, &c);
        A[e] = c;
        a = max(a, e);
    }
    scanf("%d", &m);
    for (int i = 1, e, c; i <= m; ++i) {
        scanf("%d%d", &e, &c);
        B[e] = c;
        b = max(b, e);
    }
    if (a < b) {
        puts("0 0 0.0");
        printf("%d", n);
        for (int i = 3000; i >= 0; --i)
            if (abs(A[i] - 0) > eps)
                printf(" %d %.1f", i, A[i]);
        puts("");
    } else {
        for (int i = 3000; i >= 0; --i) {
            int j, k;
            for (j = 3000; j >= 0; --j)
                if (abs(A[j] - 0) > eps)
                    break;
            for (k = 3000; k >= 0; --k)
                if (abs(B[k] - 0) > eps)
                    break;
            if (k > j)
                break;
            Q[j - k] = A[j] * 1.0 / B[k];
            for (int o = 0; o <= 3000; ++o)
                if (abs(B[o] - 0) > eps)
                    A[j - k + o] -= A[j] * 1.0 * B[o] / B[k];
        }
        out(Q);
        out(A);
    }
    return 0;
}
Last update: May 4, 2022
Back to top