多项式A除以B

这仍然是一道关于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
        ans_xishu[i] = (double) ((int)(ans_xishu[i]*10 + (ans_xishu[i]<0?-0.5:0.5)))/10;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
struct dxs{
    int zhishu;
    double xishu;
}c[33000];

bool cmp(dxs d1,dxs d2)
{
    return d1.zhishu>d2.zhishu;
}

int main()
{
//  freopen("test.in","r",stdin);
//  freopen("test.out","w",stdout);
    int a_zhishu[33000],b_zhishu[33000],temp_zhishu[33000],shuchu;
    double temp_xishu[33000],b_xishu[33000];
    double ans_xishu[33000],a_xishu[33000];
    int ans_zhishu[33000];
    bool temp_biaoji[33000],pd,vo;
    int n1,n2,i,num=0,start,tot=0;
    cin>>n1;
    for (i=1;i<=n1;i++)
      scanf("%d%lf",&a_zhishu[i],&a_xishu[i]);
    cin>>n2;
    for (i=1;i<=n2;i++)
      scanf("%d%lf",&b_zhishu[i],&b_xishu[i]);
    while (n1!=0 and a_zhishu[1]>=b_zhishu[1])
    {
        start=1;
        num++;
        ans_zhishu[num]=a_zhishu[1]-b_zhishu[1];
        ans_xishu[num]=a_xishu[1]/b_xishu[1];
        for (i=1;i<=n2;i++)
        {
            temp_zhishu[i]=ans_zhishu[num]+b_zhishu[i];
            temp_xishu[i]=ans_xishu[num]*b_xishu[i];
            temp_biaoji[i]=0;
        }
        for (i=1;i<=n1;i++)
        {
          pd=false;
          for (int j=start;j<=n2 and temp_zhishu[j]>=a_zhishu[i];j++)
            if (a_zhishu[i]==temp_zhishu[j])
            {
                pd=true;
                if (a_xishu[i]!=temp_xishu[j])
                {
                    c[++tot].zhishu=a_zhishu[i];
                    c[tot].xishu=a_xishu[i]-temp_xishu[j];
                }
                temp_biaoji[j]=1;
                start++;
                break;
            }
          if (pd==false)
          {
                c[++tot].zhishu=a_zhishu[i];
                c[tot].xishu=a_xishu[i];
          }
        }
        for (i=1;i<=n2;i++)
          if (temp_biaoji[i]==0)
          {
            c[++tot].zhishu=temp_zhishu[i];
            c[tot].xishu=(-1)*temp_xishu[i];
          }
        sort(c+1,c+tot+1,cmp);
        for (int i=1;i<=tot;i++)
        {
            a_xishu[i]=c[i].xishu;
            a_zhishu[i]=c[i].zhishu;
        }
        n1=tot;
        tot=0;
    }
    for(int i=1;i<=num;i++)
        ans_xishu[i] = (double) ((int)(ans_xishu[i]*10 + (ans_xishu[i]<0?-0.5:0.5)))/10;
    for(int i=1;i<=n1;i++)
        a_xishu[i] = (double)((int)(a_xishu[i]*10 + (a_xishu[i]<0?-0.5:0.5)))/10;
    shuchu=num;
    for (i=1;i<=num;i++)
      if (ans_xishu[i]==0)
        shuchu--;
    if (shuchu==0)
      cout<<"0 0 0.0"<<endl;
    else
    {
        vo=true;
      printf("%d ",shuchu);
      for (i=1;i<=num;i++)
        if (ans_xishu[i]!=0)
          if (vo==true)
          {
            printf("%d %.1lf",ans_zhishu[i],ans_xishu[i]);
            vo=false;
          }
          else
          printf(" %d %.1lf",ans_zhishu[i],ans_xishu[i]);
      printf("\n");
    }
    shuchu=n1;
    for (i=1;i<=n1;i++)
      if (a_xishu[i]==0)
        shuchu--;
    if (shuchu==0)
      cout<<"0 0 0.0";
    else
    {
      printf("%d ",shuchu);
      vo=true;
      for (i=1;i<=n1;i++)
        if (a_xishu[i]!=0)
          if (vo==true)
          {
            printf("%d %.1lf",a_zhishu[i],a_xishu[i]);
            vo=false;
          }
          else
            printf(" %d %.1lf",a_zhishu[i],a_xishu[i]);
    }
    return 0;
}


    
#include <cstdio>
#include <cmath>
using namespace std;
int nonNegativeNum(double c[], int start) {
    int cnt = 0;
    for (int i = start; i >= 0; i--)
        if (abs(c[i]) + 0.05 >= 0.1) cnt++;
    return cnt;
}
void printPoly(double c[], int start) {
    printf("%d", nonNegativeNum(c, start));
    if (nonNegativeNum(c, start) == 0) printf(" 0 0.0");
    for (int i = start; i >= 0; i--)
        if (abs(c[i]) + 0.05 >= 0.1)
            printf(" %d %.1f", i, c[i]);
}
double c1[3000], c2[3000], c3[3000];
int main() {
    int m = 0, n = 0, t = 0, max1 = -1, max2= -1;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &t);
        max1 = max1 > t ? max1 : t;
        scanf("%lf", &c1[t]);
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        max2 = max2 > t ? max2 : t;
        scanf("%lf", &c2[t]);
    }
    int t1 = max1, t2 = max2;
    while (t1 >= t2) {
        double c = c1[t1] / c2[t2];
        c3[t1 - t2] = c;
        for (int i = t1, j = t2; j >= 0; j--, i--) c1[i] -= c2[j] * c;
        while (abs(c1[t1]) < 0.000001) t1--;
    }
    printPoly(c3, max1 - max2);
    printf("\n");
    printPoly(c1, t1);
    return 0;
}
02-01 00:04