/**
  *  @title: chinrem.cpp
  *  @date: 2004.09.25 - 13:58
  *  @author: vinnie
  *  @source for chinrem.exe
  */

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

//  given 2 int, returns the Greatest Common Divisor
//  (euclidean theorem)
int gcd( int a, int b)
{
  int c = 0;
  while ( b != 0)
  { c = a % b;
    a = b;
    b = c;
    }
  return a;
}
//  ====================   Main   ===========================================
void main( )
{
int a1, a2, a3, m1, m2, m3;
char mystr[4];

system("color 1e");

// menu' label
MYMENU:

//  begin
system("cls");
printf(" SLCC - CS 2310-01 - Fall '04 - Prj. #1\n");
printf(" Reduced version of the Chinese Remainder.\n That means you can");
printf(" input max 3 var's.\n\n");
printf(" 1) modulii are positive\n");
printf(" 2) any modulo MAX 2 digits;\n");
printf(" 3) any 2 modulii are relatively prime;\n");
printf(" 4) you have to input ALL the 3 vars\n");
//  -------------------------------------------------------------------------

//  reset variables

a1 = a2 = a3 = 0;
m1 = m2 = m3 = 0;

gotoxy( 1, 10); printf("x = "); gets( mystr); a1 = atoi( mystr);
*mystr = '\0'; gotoxy( 8, 10); printf("( mod ") ; gets( mystr);
m1 = atoi( mystr); *mystr = '\0'; gotoxy( 16, 10); printf(")");
//==
gotoxy( 1, 11); printf("x = "); gets( mystr); a2 = atoi( mystr);
*mystr = '\0'; gotoxy( 8, 11); printf("( mod ") ; gets( mystr);
m2 = atoi( mystr); *mystr = '\0'; gotoxy( 16, 11); printf(")");
//==
gotoxy( 1, 12); printf("x = "); gets( mystr); a3 = atoi( mystr);
*mystr = '\0'; gotoxy( 8, 12); printf("( mod ") ; gets( mystr);
m3 = atoi( mystr); *mystr = '\0'; gotoxy( 16, 12); printf(")");
//  ------------------------------------------------------------------

//  check for relatively prime
if (
        1 != gcd( m1, m2)
     || 1 != gcd( m1, m3)
     || 1 != gcd( m2, m3)
   )
   {
      printf("\n2 modulos are not relatively prime\nERROR: -1\n");
      exit( -1);
   }
//  -------------------------------------------------------------

//  equations

int M, M1, M2, M3;
//  inv
int y1, y2, y3;
M = M1 = M2 = M3 = y1 = y2 = y3 = 0;

M = m1 * m2 * m3;
M1 = M / m1;
M2 = M / m2;
M3 = M / m3;

y1 = M1 % m1;
y2 = M2 % m2;
y3 = M3 % m3;

int x = ( a1*M1*y1) + ( a2*M2*y2) + ( a3*M3*y3);

int res = x % M;
//  ---------------------------------------------------------

//  print result

//printf("\n\n %d, %d, %d", a1, a2, a3);
//printf("\n %d, %d, %d", m1, m2, m3);
printf("\n\nx = %d = %d (mod %d)\n", x, res, M);
//  ---------------------------------------------------------

//  ask for an other trip

char c;
printf("\n Another one [Y/y/N/n]? ");
while ( !kbhit() );
c = getchar( );
if ( c == 'Y' || c == 'y' ) goto MYMENU;
//  ---------------------------------------------------------

printf("\n Thanks for using Chinese Remainder, project #1\n");
printf(" Vincenzo Maggio CodeŠ - released under GPL\n");

system("color 0f");
}