#include<stdio.h>

struct C_code{
  int x;
  int a;
};

main(){
  int i,j,z,flag=0;
  int n,k;
  int f;
  int s;
  struct C_code g[20];
  struct C_code m[20];
  struct C_code c[40];
  struct C_code r[20];
  struct C_code t[20];
  struct C_code q[20];
  for(i=0;i<20;i++) {g[i].x=i;g[i].a=0;}
  printf("Input (n,k):");
  scanf("%d%d",&n,&k);
  printf("Input the g(x):"); /*輸入g（x）的系數不為0的x的系數*/
  for(i=n-k;i>=0;i--)
  {
    scanf("%d",&f);
    g[i].a=f;
  }
  for(i=n-k;i>=0;i--) { if(i==n-k)printf("g(x):"); printf("%d",g[i].a);} printf("\n");/*測試*/
  leap:
  for(i=0;i<40;i++){
    if(i<20){
      m[i].x=i;m[i].a=0;
      c[i].x=i;c[i].a=0;
      r[i].x=i;r[i].a=0;
      t[i].x=i;t[i].a=0;
      q[i].x=i;q[i].a=0;
    }
    else{
      c[i].x=i;c[i].a=0;
    }
  }
  if(flag==0){
  printf("Input the m(x):"); /*輸入m（x）x的次數的系數*/
  flag=1;
  }
  for(i=k-1;i>=0;i--){
    scanf("%d",&f);
    m[i].a=f;
  }
  for(i=k-1;i>=0;i--){ if(i==k-1)printf("m(x):"); printf("%d",m[i].a);} /*測試*/
  printf("\n");
  for(i=k-1;i>=0;i--){    /*把m（x）乘以x的n-k次方存到t(x)*/
     if(m[i].a==1){
       t[i+n-k].a=1;
     }
  }
  for(i=n-1;i>=0;i--) { if(i==n-1)printf("t(x):"); printf("%d",t[i].a);}  printf("\n");/*測試*/

 /*用g（x）去除t（x），得到余式r（x）*/
  while(1){
    j=n-1;
    while(t[j].a==0) j--;
    for(i=0;i<20;i++) {q[i].x=i;q[i].a=0;}
    printf("j:%d\n",j);
    if(j<n-k) break;
    else{
      s=t[j].x-g[n-k].x;
      printf("s %d:%d",j,s);printf("\n"); /*測試*/
      for(i=n-k;i>=0;i--){    /*用q(x)存每次商與g(x)的乘積*/
        if(g[i].a==1){
          q[i+s].a=1;
        }
      }
      for(i=n-1;i>=0;i--){ if(i==n-1)printf("q(x) %d:",j); printf("%d",q[i].a);} printf("\n"); /*測試*/
      for(i=j;i>=0;i--){     /*把t(x)每次與q(x)的mod2和修改t(x)的值*/
        t[i].a=(t[i].a+q[i].a)%2;
        r[i].a=t[i].a;
      }
      for(i=n-1;i>=0;i--){ if(i==n-1)printf("t(x) %d:",j); printf("%d",t[i].a);} printf("\n"); /*測試*/
    }
  }
  for(i=n-k-1;i>=0;i--){ if(i==n-k-1)printf("r(x):"); printf("%d",r[i].a);} printf("\n"); /*測試*/
  for(i=n-k-1;i>=0;i--){ if(i==n-k-1)printf("t(x):"); printf("%d",t[i].a);} printf("\n"); /*測試*/
 /*以r（x）作為監督多項式附加在xr *M（x）之后，得到所需的碼組。*/
  for(i=n-1 ;i>=0;i--){
    if(i>=k){
      c[i].a=m[i-n+k].a;
    }
    else{
      c[i].a=r[i].a;
    }
  }
 for(i=n-1;i>=0;i--){
   if(i==n-1) printf("\tThe code:");
   printf("%d",c[i].a);
 }
 printf("\nNext m(x):");
 goto leap;
 getch();
}