/* [bo][it]题目-要求[/it][/bo]
[bo][un]Description[/un][/bo]
一个一元多项式可以看作由若干个一元单项式按降幂排列成的线性表。请编写程序对输入的两个一元多项式求积，并输出求积的结果。
[bo][un]Input[/un][/bo]
输入为两个一元多项式， 每个一元多项式输入一行，按照降幂依次输入每个单项式的系数和指数，并以-1 -1作为结束。
系数和指数均为整数，指数不小于0。
[bo][un]Output[/un][/bo]
输出为求积结果多项式，按照降幂依次输出每个单项的系数和指数，每个数值后面用一个空格隔开，输出结果多项式后换行。
系数为0的单项式不得输出——除非结果多项式就是0，则直接输出0。
[bo][un]Sample Input[/un][/bo]
2 5 1 0 -1 -1
5 4 3 0 -1 -1
[bo][un]Sample Output[/un][/bo]
10 9 6 5 5 4 3 0
*/

#include<stdio.h>
typedef struct multi{
    int a;
    int b;
    struct multi *next;
}*mult;

mult Init(){//初始化 
    mult L;
    L = new multi;
    return L;
}

mult Input(mult L){//接收输入数据 
    int ia;
    int ib;
    mult p = L;
    
    while(1){
        scanf("%i %i", &ia, &ib);
        if(ia == -1 && ib == -1){
            break;
        }else if(ia == 0){
            continue;
        }else{
            p->next = new multi;
            
            p->next->a = ia;
            p->next->b = ib;
            p = p->next;            
        }
    }
    return L;
}

mult Deal(mult L1, mult L2){//处理 ,把结果保存在新建的L3里 
    mult p1 = L1;
    mult p2 = L2;
    mult L3 = Init();
    mult p3 = L3;
    int n = 0;//记录有效结点数 
    while(p1->next != NULL){//2个多项式相乘 
        while(p2->next != NULL){
            p3->next = new multi;
            p3->next->a = p1->next->a * p2->next->a;
            p3->next->b = p1->next->b + p2->next->b;
            n++;
            p2 = p2->next;
            p3 = p3->next;
        }
        p2 = L2;
        p1 = p1->next;
    }

    
//    p3 = L3;
//    while(p3->next != NULL){//???***
//        printf("%i %i ", p3->next->a, p3->next->b);
//        p3 = p3->next;
//    }
//    printf("\nn = %i\n", n);
    
    p3 = L3;    
    int tempa;
    int tempb;
    for(int i = 1; i < n; i++){//排序 递减 
        for(int j = 1; j <= n-i; j++){
            if(p3->next->b < p3->next->next->b){//前小后大，就交换数据 
                tempa = p3->next->a;
                tempb = p3->next->b;
                p3->next->a = p3->next->next->a;
                p3->next->b = p3->next->next->b;
                p3->next->next->a = tempa;
                p3->next->next->b = tempb;
//            }else if(p3->next->b == p3->next->next->b){
                
            }
            p3 = p3->next;                
        }
        p3 = L3;
    }
    
    mult k;
    p3 = L3; 
    while(p3->next != NULL && p3->next->next != NULL){//对指数相同的结点 合并 删除前结点  
        if(p3->next->b == p3->next->next->b){
            p3->next->next->a += p3->next->a;
            k = p3->next;
            p3->next = k->next;
            k->next = NULL;
        }else{
            p3 = p3->next;
        }
    }
    
    p3 = L3;

    while(p3->next != NULL){//对系数是0的结点删除 
        if(p3->next->a == 0){
            k = p3->next;
            p3->next = k->next;
            k->next = NULL;
        }else{
            p3 = p3->next;
        }
    }
    return L3;
    
}

void Output(mult L){//输出 
    mult p = L;
    if(p->next == NULL){
        printf("0\n");
        return;
    }
    while(p->next != NULL){
        printf("%i %i ", p->next->a, p->next->b);
        p = p->next;        
    }
    printf("\n");
    return;
}

int main(){
    mult Init();//初始化 
    mult Input(mult L);//输入 
    mult Deal(mult L1, mult L2);//处理 
    void Output(mult L);//输出 
    
    mult L1;
    L1 = Init();
    L1 = Input(L1);    
    mult L2;
    L2 = Init();
    L2 = Input(L2);
    
    L1 = Deal(L1, L2);
    Output(L1);
    
    getchar();//
    getchar();//为什么这里要有2个getchar才能显示，使命令提示符不一闪而过
    return 1;
}

//用Dev-cpp通过，可用，但太耗时间了，大家看看如何优化

//主要看如何优化，

大家看下，如何优化，减少运行时间

最近在写一元多项式相加都非常吃力，这个不会