/* ReduceIntMat.c */

#include <stdio.h>

int ReduceIntMat(int,int*);
void DisplayMat(int*);
int GCD(int,int);

void main(void)
{
 int X=54,Y,

 Mat[] = {203,48,36, 120,30, 60,66};

  printf("Fraction before matrix = (1/%d)\n",X);
  puts("Matrix = ");
 DisplayMat(Mat);



 Y = ReduceIntMat(X,Mat);
 if (X==Y) puts("No reduction of integers");
 else
  {
   printf("\nReduced fraction before matrix = (1/%d)\n",Y);
   puts("Reduced matrix =");
   DisplayMat(Mat);
  }
  
 getchar();
}

/*******************************************************************/
/* Used for inverse of an integer matrix;
 1/X is a fraction before a matrix,  p -> linear matrix array;
   return  1/Y before reduced matrix,   Y = X/GCD(X,*P) */

int ReduceIntMat(int X, int *P)      /* */
{
 int H,J,M,N,MN,    *PP;

 PP=P;  P++;

 M = *PP/100; N = *PP%100;   MN = M*N;

 H = X;

 for (J=1; J<=MN; J++)  {H = GCD(H,*P);  if (H==1) return X;  P++;}

   P=PP;  P++;
   for (J=1; J<=MN; J++) {*P /= H; P++;}

 return X/H;
}

/***********************************************************************/

int GCD(int X,int Y)
/* input two integers X,Y; return their greatest common divisor */
{
 int R;

 if (X<0) X=-X; if (Y<0) Y=-Y;
 if (X>Y) {R=X; X=Y; Y=R;}
 R=-1;
 while (R)
  {
   R=Y%X; /* Q=Y/X; printf("X=%d  Y=%d  Q=%d  R=%d\n",X,Y,Q,R); getchar(); */
   Y=X; X=R;
  }
 return Y;
}

/************************************************************************/

void DisplayMat(int *P)
 {
  int I,J,K,M,N,Max=0,T;    char S1[] = "%1d%2d%3d%4d%5d%6d%7d%8d%9d",S2[3];

  M=*P/100;  N=*P%100;  P++;
  for (I=1; I<=M; I++)
   {
    for (J=1; J<=N; J++)
     {
      if (*P>=0) K=*P; else K=-*P;
      if (K>Max) Max=K;
    }
  }

 T=1; K=1;
 while (T<=Max) {T=T*10; K++;}   K++;
 for (I=0; I<3; I++) S2[I] = S1[3*K+I];  S2[3]='\0';


 for (I=1; I<=M; I++)
   {
    for (J=1; J<=N; J++) {printf(S2,*P); P++;}
    puts("");
  }

 return;
}