#include <stdio.h>
#include <math.h>
#define SIZE 100

/*
多項式を扱うとき，p[0]に次数を格納し，p[1]に定数項を
p[2]にxの係数を，
・・・・・・・・
p[k]にx^k-1の係数を格納する．*/

void cp_poly(int p[],int q[]); /*pの配列をqにコピーする*/
void normalize_poly(int p[]);  /*多項式が2x + 4のような場合，2で割り，多項式x+2をpに代入する関数*/
void mul_poly(int p[],int a);  /*多項式に整数をかける関数．結果はpに格納．*/
void shift_poly(int p[],int n); /*多項式にx^nをかける関数．掛け算の結果をpに格納．*/
void minus_poly(int p[],int q[]); /*多項式の引き算をする関数．p-qをする．結果はpに格納する．ただし，pの次数 >= qの次数とする．*/
void div_poly(int p[],int q[],int rem[]); /*多項式の割り算p/qをする関数．再帰を行う．余りはremに格納．*/
void gcd_poly(int p[],int q[],int gcd[]); /*最大公約多項式を求める関数．最大公約多項式をgcdに格納する．*/
void print_poly(int p[]); /*多項式を表示する関数*/
int gcd(int m,int n);     /*最大公約数を求める関数*/
int lcm(int m,int n);     /*最小公倍数を求める関数*/

void cp_poly(int p[],int q[])
{
  int i;
  for(i = 0; i < SIZE;i++) q[i] = p[i];
}

void normalize_poly(int p[])
{
  int i;
  int G ;
  /*pが0次式なら多項式1とする*/
  if(p[0] == 0) p[1] = 1;
  else{
    /*pの係数の最大公約数を求める*/
    G = gcd(p[1],p[2]);
    for(i = 3;i <= p[0]+1;i++){
      G = gcd(p[i],G);
    }
    /*最大次の係数が正の時は各係数をGで割る*/
    if(p[p[0]+1] > 0) 
      for(i = 1; i <= p[0]+1;i++) p[i] = p[i]/G;
    /*最大次の係数が負の時は各係数をGで割った結果に-1をかける*/
    else if(p[p[0]+1] < 0) 
      for(i = 1; i <= p[0]+1;i++) p[i] = -1 * p[i]/G;
  }
}

void mul_poly(int p[],int a)
{
  int i;
  /*a = 0の時は0を返す*/
  if(a == 0){
    p[0] = 0;      /*次数を0とする*/
    p[1] = 0;
  }
  else for(i = 1;i <= p[0]+1;i++) p[i] = a*p[i];
}

void shift_poly(int p[],int n)
{
  int i;
  int tmp[SIZE];
  tmp[0] = p[0]+n;
  for(i = 1;i <= n;i++) tmp[i] = 0;
  for(i = n+1;i <= p[0]+1+n;i++) tmp[i] = p[i-n];
  cp_poly(tmp,p);
}

void minus_poly(int p[],int q[])
{
  int i;
  int degree = 0;
  for(i = 1;i <= p[0]+1 && i <= q[0]+1;i++){
    p[i] = p[i] - q[i];
  }
  /*引き算を行うと次数が変わる可能性があるので次数を調べる*/
  for(i = 1;i <= p[0]+1 || i <= q[0]+1;i++){
    if(p[i] != 0) degree = i-1;
  }
  p[0] = degree;
}

void div_poly(int p[],int q[],int rem[])
{
  int L;
  int tmp_q[SIZE]; /*qをコピーを保存する配列*/
  if(p[0] < q[0]) cp_poly(p,rem);
  else if(p[0] == 0 && p[1] == 0){
    rem[0] = 0;
    rem[1] = 0;
  }
  else {
    L = lcm(p[p[0]+1],q[q[0]+1]);
    cp_poly(q,tmp_q);
    mul_poly(p,L/p[p[0]+1]);
    mul_poly(tmp_q,L/tmp_q[tmp_q[0]+1]);
    shift_poly(tmp_q,p[0] - tmp_q[0]);
    minus_poly(p,tmp_q);
    div_poly(p,q,rem);
  }
}

void gcd_poly(int p[],int q[],int gcd[])
{
  int rem[SIZE];
  if(q[0] == 0 && q[1] == 0){
    cp_poly(p,gcd);
    normalize_poly(gcd);
  }
  else {
    div_poly(p,q,rem); 
    gcd_poly(q,rem,gcd);
  }
}

void print_poly(int p[])
{
  int i;
  /*次数の大きい方から3x^n + 4x^n-1 + ...のように表示*/
  for(i = p[0];i > 1;i--){
    if (p[i+1]==0) continue;
    if (p[i+1]==1) printf("x^%d + ",i);
    else printf("%dx^%d + ",p[i+1],i);
  }
  if (p[2]!=0) 
     if (p[2]==1) printf("x + ",p[2]);
     else printf("%dx + ",p[2]);
  if (p[1]!=0) printf("%d\n",p[1]);
  return;
}

int gcd(int m,int n)
{
  int ret;
  m = abs(m);
  n = abs(n);
  if(n == 0) ret = m;
  else ret = gcd(n,m%n);
  return ret;
}

int lcm(int m,int n)
{
  m = abs(m);
  n = abs(n);
  int G = gcd(m,n);
  return n/G*m;
}

main()
{  
  int p[SIZE],q[SIZE],gcd[SIZE];
  int i;

  /*多項式pとqの入力*/
  /*pの引数の入力*/
  printf("p degree = ");
  scanf("%d",&p[0]);
  /*pの係数の入力*/
  puts("input p factor");
  for(i = 0;i <= p[0];i++){
    printf("a_%d = ",i);
    scanf("%d",&p[p[0]+1-i]);
  }
  if(p[p[0]+1] == 0){            /*最高次の係数が0ならエラー*/
    printf("invalid input.\n");
    return 0;
  }
  /*qの引数の入力*/
  printf("q degree = ");
  scanf("%d",&q[0]);
  /*qの係数の入力*/
  puts("input q factor");
  for(i = 0;i <= q[0];i++){
    printf("b_%d = ",i);
    scanf("%d",&q[q[0]+1-i]);
  }
  if(q[q[0]+1] == 0){            /*最高次の係数が0ならエラー*/
    printf("invalid inpu.t\n");
    return 0;
  }
  /*入力した多項式の表示*/
  printf("p(x) = ");
  print_poly(p);
  printf("q(x) = ");
  print_poly(q);

  gcd_poly(p,q,gcd);  
  /*最大公約多項式の表示*/
  printf("gcd(x) = ");
  print_poly(gcd);
  return 0;
}