Page 35 - MATINF Nr. 13-14

a
Teorema chinezeasc˘ a resturilor 35

long long invers(long long a, long long m)
{
long long x, y;
long long d = euclidExtins(a, m, x, y);
if (d!=1) return 0; // Nu exista invers
return (x%m+m)%m; // Asigura rezultat pozitiv
}

// Structura pentru o congruenta: x = rest (mod modul)
struct Congruenta
{
long long rest;
long long modul;
};

// Rezolva doua congruente: x = a1 (mod m1), x = a2 (mod m2)
// Returneaza solutia sub forma {rest, modul} sau {0, 0} daca nu exista
Congruenta rezolvaDouaCongruente(long long a1,long long m1,long long a2,long long m2)
{
// Verifica compatibilitatea
long long d=cmmdc(m1, m2);
if (a1%d != a2%d) return {0, 0}; // Incompatibile

// Calculam noul modul
long long modulNou = m1/d*m2; // cmmmc(m1, m2)

// Ajustam resturile
a1%=m1; a2%=m2;

// Cautam solutia prin substitutie
// x=m1*t+a1; m1*t+a1=a2(mod m2); m1*t=(a2-a1)(mod m2)
long long a=m1, b=m2, c=(a2-a1)%m2;
if (c<0) c+=m2;

// Simplificam ecuatia impartind la d
a/=d; b/=d; c/=d; //=> a*t=c(mod b)

// Acum a si b sunt prime intre ele
// Determinam inversul modular al lui a (mod b)
long long inv_a=invers(a%b, b);
long long t = (inv_a*c)%b;
long long x = m1*t+a1;

// Asigura solutia minima pozitiva
x=((x%modulNou)+modulNou)%modulNou;

return {x, modulNou};
}

// Rezolva sistemul general de congruente prin metoda substitutiei
// Returneaza perechea {solutie, modul_final} sau {0, 0} daca nu exista