#include <stdio.h>
#define LAENGE 3

void Initialisiere(long MM[LAENGE], long BBasis[LAENGE], long AA[LAENGE])
{
	short i=0; 
	for(i=0;i<LAENGE;i++)
	{
		MM[i]=1;
		BBasis[i]=0;
		AA[i]=0;
	}
	return;  
}


 /* Die folgende Funktion gibt von Zahl modulo mod die
   Standarddarstellung modulo mod zurueck */

long Reduziere(long Zahl, long mod)
{
	while(Zahl<0)
		Zahl=Zahl+mod;
    
	while(Zahl>=mod)
		Zahl=Zahl-mod;
    
	return(Zahl);
}
  
  
/* ggT1 gibt den ggT zurueck */ 

long ggT1(long ZahlA, long ZahlB) /*gibt ggT zurueck*/
{
	long  A=0,AV,AVV;
 
	AV=ZahlB;
	AVV=ZahlA;
 
	do
	{
     
		A= Reduziere(AVV, AV);  /* Die Reduziere-Funktion wirkt genauso wie der modulo-Operator */

		AVV=AV;  AV=A;  A=0;

	} while(AV!=0);  
 
 /* ggT von ZahlA,ZahlB: AVV*/

 
	return(AVV);
   
}
 
 
/* ggT2 gibt den Koeffizienten in der ggT-Darstellung vor der zweiten
   eingegebenen Zahl zurueck */ 
 
 
long ggT2(long ZahlA, long ZahlB)  /*gibt Faktor vor ZahlA zurueck zurueck*/
{
	long Q=0,A=0,AV,AVV,R=0,RV=0,RVV=1;
 
	AV=ZahlB;
	AVV=ZahlA;
 
	do
	{
		A=Reduziere(AVV, AV);  /* Die Reduziere-Funktion wirkt genauso wie der modulo-Operator */ 
		Q=(AVV-A)/AV;
		R=RVV-RV*Q;

		AVV=AV;  AV=A;  A=0;

		RVV=RV;  RV=R;  R=0;
	}  while(AV!=0);  
 
 /* ggT von ZahlA,ZahlB: AVV*/
 /* Darstellung: ggT=     RVV* ZahlA + SVV * ZahlB                  */
 
	return(RVV);
  
 
}
 



/* ------------------------------------------ */
 
 
int main(void)
{
	long m=1,loesung;
	long M[LAENGE], Basis[LAENGE], A[LAENGE] ;
	short i=0, j=0, laenge=LAENGE, frage=1;
   
	Initialisiere(M,Basis,A);
   
/*Eingabeteil fuer die Modulzahlen*/   
   
	printf("Implementierung des chinesischen Restsatzes\nWir koennen mit maximal %hi Faktoren im kartesischen Produkt arbeiten.\n\
Geben Sie nun die Module ein. Natuerliche Zahlen groesser oder gleich 2 für echte Faktoren; 1 für triviale Faktoren.\n\
Alle diese Zahlen muessen paarweise teilerfremd sein.\n",laenge);
   
	for(i=0;i<laenge;i++)
	{
		printf("Geben Sie die %hi. Modulzahl ein: ",(i+1));
		scanf("%li",&M[i]);
	
		while(M[i]<1)
		{
			printf("Noch einmal ordentlich: ");
			scanf("%li",&M[i]);
		}
			    
		for(j=0;j<i;j++)
		{         
			if(ggT1(M[i],M[j])!=1)		       
			{
				printf("Das Programm wird beendet, da die eingegebene Modulzahl nicht teilerfremd zu den vorhergenden ist.\n");
				return(1);
			}
		       
		}
		m=m*M[i];     
	}
   
	printf("Berechnung der Loesungsbasis:\n");
   
/* Berechnung der Loesungsbasis */   
   
	for(i=0;i<laenge;i++)
	{
		Basis[i]=1-M[i]*ggT2(M[i],m/M[i]);
		printf("%hi. Basisloesungszahl: %li.\n",(i+1),Basis[i]);
	}
      
/* Urbilder gem. chin. Restsatz */      

	printf("Wir koennen jetzt leicht Urbilder unter der chinesischen Restsatzabbildung berechnen.\n");
    
	while(frage==1)
	{
		printf("Geben Sie bitte den Bildvektor mit %hi Komponenten ein.\n",laenge);
  
   
		for(i=0;i<laenge;i++)
		{
			printf("Geben Sie die %hi. Komponente ein: ",(i+1));
			scanf("%li",&A[i]);
		}
      
      
		loesung=0;
        
		for(i=0;i<laenge;i++)
			loesung=loesung+Basis[i]*A[i];
      
      
		printf("Das Urbild Ihres Vektors lautet: %li.\n", Reduziere(loesung, m));  
   
		printf("Falls Sie noch ein Urbild berechnen wollen, geben Sie nun eine 1, sonst eine 0 ein: ");
		scanf("%hi",&frage);
	}
  
  
  
	return(0);
   
}