多項式加法與乘法
===

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Term {
    int coef;
    int exp;
};

bool compareTerms(const Term& a, const Term& b) {
    return a.exp > b.exp;
}
int main(void) {
    vector<Term> poly1, poly2, polyAdd, polyMult;
    int coef, exp;

    // Input for the first polynomial
    cin >> coef;
    while (coef != -1) {
        cin >> exp;
        poly1.push_back({ coef, exp });
        cin >> coef;
    }
    sort(poly1.begin(), poly1.end(), compareTerms);
    // Input for the second polynomial
    cin >> coef;
    while (coef != -1) {
        cin >> exp;
        poly2.push_back({ coef, exp });
        cin >> coef;
    }
    sort(poly2.begin(), poly2.end(), compareTerms);
    // Add
    auto it1 = poly1.begin(), it2 = poly2.begin();
    while (it1 != poly1.end() && it2 != poly2.end()) {
        if (it1->exp == it2->exp) {
            polyAdd.push_back({ it1->coef + it2->coef, it1->exp });
            ++it1;
            ++it2;
        }
        else if (it1->exp > it2->exp) {
            polyAdd.push_back(*it1);
            ++it1;
        }
        else {
            polyAdd.push_back(*it2);
            ++it2;
        }
    }

    while (it1 != poly1.end()) {
        polyAdd.push_back(*it1);
        ++it1;
    }

    while (it2 != poly2.end()) {
        polyAdd.push_back(*it2);
        ++it2;
    }
    sort(polyAdd.begin(), polyAdd.end(), compareTerms);
    // Multiply
    for (const auto& term1 : poly1) {
        for (const auto& term2 : poly2) {
            int resultCoef = term1.coef * term2.coef;
            int resultExp = term1.exp + term2.exp;
            bool found = false;

            for (auto& term : polyMult) {
                if (term.exp == resultExp) {
                    term.coef += resultCoef;
                    found = true;
                    break;
                }
            }

            if (!found) {
                polyMult.push_back({ resultCoef, resultExp });
            }
        }
    }
    sort(polyMult.begin(), polyMult.end(), compareTerms);
    // Output
    cout << "add = ";
    for (const auto& term : polyAdd) {
        cout << term.coef;
        if (term.exp > 0) {
            cout << "x";
            if (term.exp > 1)
                cout << "^" << term.exp;
        }
        if (&term != &polyAdd.back()) {
            cout << " + ";
        }
    }
    cout << endl;

    cout << "mult = ";
    for (const auto& term : polyMult) {
        cout << term.coef;
        if (term.exp > 0) {
            cout << "x";
            if (term.exp > 1)
                cout << "^" << term.exp;
        }
        if (&term != &polyMult.back()) {
            cout << " + ";
        }
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <string>
using namespace std;


struct Link_list {
   int coef;
   int exp;
    Link_list* nex;
};
int main(void) {
    
        Link_list* head1=new(Link_list), * head2 = new(Link_list), * heada = new(Link_list), * headm = new(Link_list);
       
        head1->nex = NULL;
        head2->nex = NULL; heada->nex = NULL; headm->nex = NULL;
        Link_list * pos1 = head1, * pos2 = head2 ,* posa = heada;
        int coef, exp;
        int max = 0;
        cin >> coef;
        while (coef != -1) {
            cin >> exp;
            Link_list* p = new(Link_list);
            p->coef = coef;
            p->exp = exp;
            bool done = false;
            for (pos1 = head1; pos1->nex != NULL; pos1 = pos1->nex) {
                if (p->exp > pos1->nex->exp) {
                    p->nex = pos1->nex;
                    pos1->nex = p;
                    done = true;
                    break;
                }
            }
            if (!done) {
                p->nex = pos1->nex;
                pos1->nex = p;
            }
            cin >> coef;
        }
        cin >> coef;
        while (coef != -1) {
            cin >> exp;
            Link_list* p = new(Link_list);
            p->coef = coef;
            p->exp = exp;
            bool done = false;
            for (pos2 = head2; pos2->nex != NULL; pos2 = pos2->nex) {
                if (p->exp > pos2->nex->exp) {
                    p->nex = pos2->nex;
                    pos2->nex = p;
                    done = true;
                    break;
                }
            }
            if (!done) {
                p->nex = pos2->nex;
                pos2->nex = p;
            }
            cin >> coef;
        }

        //add
        pos1 = head1->nex; pos2 = head2->nex;
        while (pos1 != NULL && pos2 != NULL) {
            if (pos1->exp == pos2->exp) {
                Link_list* p = new(Link_list);
                p->coef = pos1->coef + pos2->coef;
                p->exp = pos1->exp;
                p->nex = posa->nex;
                posa->nex = p;
                posa = p;
                pos1 = pos1->nex;
                pos2 = pos2->nex;
            }
            else if (pos1->exp > pos2->exp ) {
                Link_list* p = new(Link_list);
                p->coef = pos1->coef ;
                p->exp = pos1->exp;
                p->nex = posa->nex;
                posa->nex = p;
                posa = p;
                pos1 = pos1->nex;
            }
            else if (pos1->exp < pos2->exp) {
                Link_list* p = new(Link_list);
                p->coef =  pos2->coef;
                p->exp = pos2->exp;
                p->nex = posa->nex;
                posa->nex = p;
                posa = p;
                pos2 = pos2->nex;
                
            }
            
        }
        while (pos1 != NULL) {
            Link_list* p = new(Link_list);
            p->coef = pos1->coef;
            p->exp = pos1->exp;
            p->nex = posa->nex;
            posa->nex = p;
            posa = p;
            pos1 = pos1->nex;
        }
        while (pos2 != NULL) {
            Link_list* p = new(Link_list);
            p->coef = pos2->coef;
            p->exp = pos2->exp;
            p->nex = posa->nex;
            posa->nex = p;
            posa = p;
            pos2 = pos2->nex;
        }
        
        //mult
        Link_list* pos = headm->nex;
        for (pos1 = head1->nex; pos1 != NULL; pos1 = pos1->nex) {
            for (pos2 = head2->nex; pos2 != NULL; pos2 = pos2->nex) {
                exp = pos1->exp + pos2->exp;
                bool done = false;
                for (pos = headm; pos->nex != NULL; pos = pos->nex) {
                    if (pos->nex->exp == exp) {
                        pos->nex->coef += pos1->coef * pos2->coef;
                        done = true;
                        break;
                    }
                    else if (exp > pos->nex->exp) {
                        Link_list* p = new(Link_list);
                        p->coef = pos1->coef * pos2->coef;
                        p->exp = exp;
                        p->nex = pos->nex;
                        pos->nex = p;
                        done = true;
                        break;
                    }
                }
                if (!done) {
                    Link_list* p = new(Link_list);
                    p->coef = pos1->coef * pos2->coef;
                    p->exp = exp;
                    p->nex = pos->nex;
                    pos->nex = p;
                }
            }
        }

        //output
        cout << "add = ";
        for (Link_list* p = heada->nex; p != NULL; p = p->nex) {
            cout << p->coef;
            if (p->exp > 0) {
                cout << "x";
                if (p->exp > 1) cout << "^" << p->exp;
            }
               
            if (p->nex != NULL) {
                cout << " + ";
            }
        }
        cout << endl;
        cout << "mult = ";
        for (Link_list* p = headm->nex; p != NULL; p = p->nex) {
            cout << p->coef;
            if (p->exp > 0) {
                cout << "x";
                if (p->exp > 1) cout << "^" << p->exp;
            }
            if (p->nex != NULL) {
                cout << " + ";
            }
        }
        cout << endl;
    

    return 0;
}