Page 36 - MATINF Nr. 13-14

36 V. P˘aun

Congruenta TCR(Congruenta congruente[],int k) ///rezolva k congruente
{
if (k==0) return {0, 1}; // Sistem vid -> orice x e solutie

// Combinam congruentele una cate una
long long xCurent=congruente[0].rest%congruente[0].modul;
long long modulCurent=congruente[0].modul;
for (int i=1; i<k; i++)
{ Congruenta rez = rezolvaDouaCongruente(xCurent, modulCurent,
congruente[i].rest % congruente[i].modul, congruente[i].modul);

if (rez.rest==0) return {0, 0}; ///Eroare la combinarea cu congruenta i
xCurent=rez.rest;
modulCurent=rez.modul;
}
return {xCurent, modulCurent};
}

// Functie pentru afisare ajutatoare
void afiseaza_rezultat(Congruenta rezultat)
{
if (rezultat.rest==0) cout<<''Sistemul NU are solutie!''<<endl;
else cout<<endl<<''Solutia sistemului: x = ''<<rezultat.rest
<<'' (mod ''<<rezultat.modul<<'')'' << endl;
cout<<''========================''<<endl<<endl;
}

int main()
{
cout<<''=== TEOREMA CHINEZA A RESTURILOR ===''<<endl;
cout<<''Metoda substitutiei''<<endl;

// === TEST 1: Sistem compatibil cu module prime intre ele===
cout<<''TEST 1: Sistem cu module prime intre ele''<<endl;

Congruenta test1[] = { {2, 3}, {3, 5}, {2, 7} };
// x = 2 (mod 3); x = 3 (mod 5); x = 2 (mod 7)

cout << ''Sistemul:'' << endl;
for(int i=0; i<3; i++)
cout<<'' x=''<<test1[i].rest<<'' (mod ''<<test1[i].modul<<'')''<<endl;
Congruenta rez1 = TCR(test1,3);
afiseaza_rezultat(rez1);

// === TEST 2: Sistem compatibil cu module neprime intre ele ===
cout<<''TEST 2: Sistem compatibil cu module neprime intre ele'' << endl;

Congruenta test2[] = {{3, 4},{5, 6}, {7, 8} };
// x = 3 (mod 4); x = 5 (mod 6); x = 7 (mod 8)

cout<<''Sistemul:''<<endl;