#include<stdio.h>

typedef  enum {FALSE=0, TRUE=1} boolean;


int  nwd (int n, int k) {
  int z;
  if (n<k) {
    z=n; n=k; k=z;
  }
  while (k != 0) {
    z=k; k = n%k; n=z;
  }
  return n;
}


int  wyn (int n, int m[n], int a[n]) {
  boolean rowne;
  do {
    rowne=TRUE;
    int  i, min=0;
    for (i=1; i<n; i++)
      if (a[i] != a[min]) {
        rowne=FALSE;
        if (a[i] < a[min])
  	min = i;
      }
    if (!rowne)  a[min] += m[min];
  }  while (!rowne);
  return a[0];
}


int  main () {
  int  n, i, j, M;
  printf("\nCHINSKIE TWIERDZENIE O RESZTACH\n");
  printf("Ile kongruencji?  ");  scanf("%i", &n);
  if (n < 1) {
    printf("\nNIE MA KONGRUENCJI\n\n"); return 0;
  }

  int m[n], a[n];
  if (n == 1)
    printf("\nPodaj 1 kongruencje postaci  x mod <modul> == <reszta> :\n\n");
  else
    if (1 <= n%10 && n%10 < 5)
      printf(
        "\nPodaj %i kongruencje postaci  x mod <modul> == <reszta> :\n\n",
        n
      );
    else
      printf(
        "\nPodaj %i kongruencji postaci  x mod <modul> == <reszta> :\n\n",
        n
      );

  for (i=0; i<n; i++) {
    printf("  kongr. nr %i:  x mod ", i); scanf("%i", &m[i]);
    printf("                          == "); scanf("%i", &a[i]);
    if (0>a[i] || a[i]>=m[i]) {
      printf("!!! reszta musi byc nieujemna i mniejsza od modulu !!!\n\n");
      i--;
    }
    else {
      j=0;
      while (j<i && nwd(m[j],m[i]) == 1)  j++;
      if (j<i) {
	printf(
          "!!! moduly  %i  i  %i  nie sa wzgl. pierwsze !!!\n\n",
          m[j], m[i]
        );
	i--;
      }
    }
  }

  M=1;
  for (i=0; i<n; i++)
    M *= m[i];

  printf("\nROZWIAZANIEM UKLADU KONGRUENCJI:\n\n");
  for (i=0; i<n; i++)
    printf("  x mod %4i == %4i\n", m[i], a[i]);
  printf("\nJEST\n");
  printf("\n  x  ==  %i + %i*k  dla dow. calkowitego  k\n\n", wyn(n,m,a), M);

  return 0;
}