#include<iostream>



using namespace std;



class czynnik

{

  public:

  int wspolczynnik;

  int potega;

  czynnik();



};



class wielomian

{

    public:

    int wielkosc;

    czynnik * wielomian;

};



czynnik * przepisz_wielomian(int wielkosc, czynnik*wielomian);

czynnik * wpisz_wielomian(int wielkosc, czynnik * wielomian);

czynnik * sortuj_potegi_wielomianu(int wielkosc, czynnik * wielomian);

void wypisz_wielomian(int wielkosc, czynnik * wielomian);

czynnik * odejmowanie_wielomianow(int wielkosc, czynnik *  pozostale, int wielkosc_2, czynnik * wielomian_2, czynnik * wynik);

czynnik * dzielenie_wielomianow(int wielkosc, czynnik* wielomian_1,int wielkosc_2,  czynnik* wielomian_2);





int main()

{

  czynnik * wielomian_1;



  cout << "Podaj wielkosc pierwszego wielomianu:";

  int wielkosc;

  cin >> wielkosc;

  wielomian_1 = new czynnik[wielkosc];

  wpisz_wielomian(wielkosc, wielomian_1);

  sortuj_potegi_wielomianu(wielkosc, wielomian_1);





  cout << "Podaj wielkosc drugiego wielomianu:";

  czynnik * wielomian_2;

  int wielkosc_2;

  cin >> wielkosc_2;

  wielomian_2 = new czynnik[wielkosc];

  wpisz_wielomian(wielkosc_2, wielomian_2);

  sortuj_potegi_wielomianu(wielkosc_2, wielomian_2);





  czynnik * po_dzieleniu;

  po_dzieleniu = dzielenie_wielomianow(wielkosc, wielomian_1, wielkosc_2, wielomian_2);

  cout << endl;

  wypisz_wielomian(wielkosc, po_dzieleniu);





  return 0;

}



czynnik * dzielenie_wielomianow(int wielkosc, czynnik* wielomian_1,int wielkosc_2, czynnik * wielomian_2)

{

    czynnik * bufor;



    //przypisuje buforowi pierwszy element  pierwszego wielomianu

    // sprawdza odrazu czy zachodzi warunek iz potega pierwszego wielomianu > od potegi drugiego

    //wielomianu

    if(wielomian_1->potega > wielomian_2->potega)

    {

        bufor->potega = wielomian_1->potega;

        bufor->wspolczynnik = wielomian_1->wspolczynnik;

    }

    else

    {

        return NULL;

    }





    //tworzy zmienna pomocniczna pozostale, w ktorej bedzie przechowywany wielomian

    // pozostaly z ktorego beda odejmowane skladniki w dzieleniu wielomianow pisemnym

    czynnik * pozostale;

    pozostale = new czynnik[wielkosc];

    pozostale = przepisz_wielomian(wielkosc, wielomian_1);





    wypisz_wielomian(wielkosc, pozostale);



    cout << endl;



    //zmienna pomocniczna, trzymajaca "wynik" dzielenia dwoch wielomianow

    czynnik * wynik;

    wynik = new czynnik[wielkosc+1];



    int k = 0;

    int i = 0;



    while(true)

    {



       //przypisuje wynikiwoi pierwszy wyraz pozostalego wielomianu

       //podzielonego przez pierwszy wyraz dzielacego wielomianu

      (wynik+i)->potega = (bufor)->potega - (wielomian_2 + 0)->potega;

      (wynik+i)->wspolczynnik = (bufor)->wspolczynnik / (wielomian_2 + 0)->wspolczynnik;

      if((wynik+i)->potega < (wielomian_2+0)->potega)

        break;



      //przesyla pozostaly wielomian, wielomian dzielacy, oraz aktualny wyraz wyniku,

      //aby wykonac odejmowanie wielomianow ktore jest wykonywane w trakcie dzielenia

      //dwoch wielomianow

      pozostale = odejmowanie_wielomianow(wielkosc, pozostale, wielkosc_2, wielomian_2, (wynik+i));

      wypisz_wielomian(wielkosc, pozostale);



      int l = 0;

      for(int w = 0; w < wielkosc; w++)

      {

        if((pozostale+w)->wspolczynnik != 0)

        {



          k = w;

          bufor->potega = (pozostale+w)->potega;

          bufor->wspolczynnik = (pozostale+w)->wspolczynnik;

          break;

        }



        l++;

      }



      if((l == wielkosc-1) || ( (bufor->potega) < ((wielomian_2+0)->potega) ))

      {

          break;

      }



    //warunkiem konczacym dzialanie programu jest odpowiednia potega pozostalego wielomianu

      //if(((bufor->potega) - ((wielomian_2+0)->potega)) < ((wielomian_2+0)->potega))

      i++;

    }







    (wynik+wielkosc)->potega = 0;

    (wynik+wielkosc)->wspolczynnik = 0;

    return wynik;

}



czynnik* odejmowanie_wielomianow(int wielkosc, czynnik * wielomian, int wielkosc_2, czynnik*wielomian_2, czynnik * mnozacy)

{



//dla kazdego elementu odejmujacego wielomianu

  for(int i = 0; i < wielkosc_2; i ++)

  {

    // sprawdza sie kazdy element wielomianu

    for(int j = 0; j < wielkosc; j ++)

    {

        // jak znajdzie odpowiednia potege to odejmuje wielomian

      if((wielomian+j)->potega == (((wielomian_2+i)->potega) + (mnozacy->potega)))

      {

        (wielomian+j)->wspolczynnik = (((wielomian+j)->wspolczynnik) - (((wielomian_2+i)->wspolczynnik) * (mnozacy->wspolczynnik)));

        break;

      }

    }

  }



  return wielomian;





}



czynnik * przepisz_wielomian(int wielkosc, czynnik*wielomian)

{

  czynnik * bufor;

  bufor = new czynnik[wielkosc];



  for(int i = 0; i < wielkosc; i++)

  {

    (bufor+i)->wspolczynnik = (wielomian+i)->wspolczynnik;

    (bufor+i)->potega = (wielomian+i)->potega;

  }



  return bufor;

}



void wypisz_wielomian(int wielkosc, czynnik * wielomian)

{

  for(int i = 0; i < wielkosc; i++)

  {

    cout << (wielomian+i)->wspolczynnik;

    cout << "x^";

    cout << (wielomian+i)->potega;

    cout << "  ";

  }



}



czynnik * wpisz_wielomian(int wielkosc, czynnik * wielomian)

{

  for( int w = 0; w < wielkosc; w ++)

  {

    cin>> (wielomian+w)->wspolczynnik;

    cin.get();

    cin.get();

    cin >> (wielomian+w)->potega;

  }



  return wielomian;

}



czynnik * sortuj_potegi_wielomianu(int wielkosc, czynnik * wielomian)

{

  czynnik * bufor;

  bufor = new czynnik;



  for(int i = 0; i < wielkosc-1; i ++)

  {

    for(int j = 0; j < wielkosc-1; j++)

    {

      if((wielomian+j)->potega < (wielomian+j+1)->potega)

      {

        bufor->wspolczynnik = (wielomian+j)->wspolczynnik;

        bufor->potega = (wielomian+j)->potega;



        (wielomian+j)->wspolczynnik = (wielomian+j+1)->wspolczynnik;

        (wielomian+j)->potega = (wielomian+j+1)->potega;



        (wielomian+j+1)->wspolczynnik = bufor->wspolczynnik;

        (wielomian+j+1)->potega = bufor->potega;



      }

    }

  }



  //delete bufor;



  return wielomian;

}





czynnik::czynnik()

{

  wspolczynnik = 0;

  potega = 0;

}