#include <iostream>
using namespace std;

void polyprint(int d,int f[10]);
void polyadd(int f[10],int g[10], int ans[10]);
void polysub(int f[10],int g[10], int ans[10]);
void polymultiply(int f[10],int g[10],int ans[20]);
void polydiv(int n, int a[10], int m, int b[10], int q[10], int r[10]);
int lc(int a[10]);
int deg(int a[10]);

int max(int a, int b)
{
  if(a<=b) return b;
  return a;
}

int main()
{
  int degf;
  int degg;
  int f[10];
  int g[10];
  int h[10];
  int hsub[10];
  int h2[20];
  int q[10];
  int r[10];  

  for(int i=0;i<20;i++) h2[i]=0;

  std::cout <<"Enter the degree of the polynomial:";
  std::cin >>degf;
  std::cout <<"Enter the coefficients (a_0,...a_n):\n";
  for(int i=0;i<=degf;i++)
    {
      std::cout <<"a["<<i<<"]=";
      std::cin >>f[i];
    }
  for(int i=degf+1;i<=9;i++)
    {
      f[i]=0;
    }
  std::cout <<"Enter the degree of the second polynomial:";
  std::cin >>degg;
  std::cout <<"Enter the coefficients (a_0,...a_n):\n";
  for(int i=0;i<=degg;i++)
    {
      std::cout <<"a["<<i<<"]=";
      std::cin >>g[i];
    }
  for(int i=degg+1;i<=9;i++)
    {
      g[i]=0;
    }
  for(int i=0;i<10;i++)
    {
      q[i]=0;
      r[i]=0;
    }

  cout <<"f(x)=";
  polyprint(degf,f);
  cout <<"lc(f)="<<lc(f)<<endl;
  cout <<"deg(f)="<<deg(f)<<endl<<endl;

  cout <<"g(x)=";
  polyprint(degg,g);
  cout <<"lc(g)="<<lc(g)<<endl;
  cout <<"deg(g)="<<deg(g)<<endl<<endl;

  polyadd(f,g,h);
  cout <<"f(x)+g(x)=";
  polyprint(max(degf,degg),h);
  cout <<"lc(f+g)="<<lc(h)<<endl;
  cout <<"deg(f+g)="<<deg(h)<<endl<<endl;

  polysub(f,g,hsub);
  cout <<"f(x)-g(x)=";
  polyprint(max(degf,degg),hsub);
  cout <<"lc(f-g)="<<lc(hsub)<<endl;
  cout <<"deg(f-g)="<<deg(hsub)<<endl<<endl;

  polymultiply(f,g,h2);
  cout <<"f(x)g(x)=";
  polyprint(degf*degg,h2);
  cout <<"lc(fg)="<<lc(h2)<<endl;
  cout <<"deg(fg)="<<deg(h2)<<endl<<endl;

  polydiv(degf,f,degg,g,q,r);
  cout <<"q(x)=";
  polyprint(9,q);
  cout <<"r(x)=";
  polyprint(9,r);

  return 0;
}

void polyprint(int d,int f[10])
{
  std::cout <<f[0];
  for(int i=1;i<=d;i++)
    {
      std::cout <<"+"<<f[i]<<"x^"<<i;
    }
  std::cout <<"\n";
}

void polyadd(int f[10],int g[10],int ans[10])
{
  for(int i=0;i<=9;i++)
    {
      ans[i]=f[i]+g[i];
    }
  
}

void polysub(int f[10],int g[10],int ans[10])
{
  for(int i=0;i<=9;i++)
    {
      ans[i]=f[i]-g[i];
    }
  
}

void polymultiply(int f[10],int g[10],int ans[20])
{
  int temp[10][20];
  int k=-1;
  
  for(int i=0;i<10;i++)
    {
      for(int j=0;j<20;j++)
	{
	  temp[i][j]=0;
	  //std::cout <<"temp["<<i<<"]["<<j<<"]="<<temp[i][j]<<"\n";
	}
    }

  for(int i=0;i<10;i++)
    {
      k++;
      //cout <<k<<endl;
      for(int j=0;j<10;j++)
	{
	  temp[i][j+k]=f[i]*g[j];
	  //cout <<"temp["<<i<<"]["<<j+k<<"]="<<temp[i][j+k]<<endl;
	}
    }
  for(int j=0;j<20;j++)
    {
      for(int i=0;i<10;i++)
	{
	  ans[j]+=temp[i][j];
	  //cout <<"ans["<<j<<"]="<<ans[j]<<endl;
	}
    }
}

void polydiv(int n, int a[10], int m, int b[10], int q[10], int r[10])
{
  int temp[10],temp2[10],temp3[10],xt[10];
  int x[10][10];
  int u=b[m];

  //initialize x
  for(int i=0;i<10;i++)
    {
      for(int j=0;j<10;j++)
	{
	  if(i==j) 
	    {
	      x[i][j]=1;
	    }
	  else
	    {
	      x[i][j]=0;
	    }
	}
    }  

  for(int k=0;k<10;k++) r[k]=a[k];
  for(int i=n-m;i>=0;i--)
    {
      if(deg(r)==m+i)
	{
	  q[i]=lc(r)*u;
	  //r<-r-q_i*x^i*b
	  for(int j=0;j<10;j++) xt[j]=x[i][j];	  
	  xt[i]=q[i];
	  polymultiply(xt,b,temp2);
	  polysub(r,temp2,temp3);
	  for(int k=0;k<10;k++) r[k]=temp3[k];
	}
      else
	{
	  q[i]=0;
	  cout <<"q["<<i<<"]<-0"<<endl;
	}
    }
}

int lc(int a[10])
{
  int l=a[0];

  for(int i=1;i<10;i++)
    {
      if(a[i] != 0) l=a[i];
    }
  return l;
}

int deg(int a[10])
{
  int l=-1;
  
  for(int i=1;i<10;i++)
    {
      if(a[i] != 0) l=i;
    }

  return l;
}