Page 44 - MATINF Nr. 11-12

44 V. P˘aun

if(a==0){m=0,n=1; return b;}
if(a>0 && b>0) return _cmmdcExtins (a,b,m,n);
if(a<0 && b <0){d= _cmmdcExtins(-a,-b,m,n); m=-m;n=-n; return d;}
if(a <0){d=_cmmdcExtins(-a,b,m,n); m=-m; return d;}
if(b <0){d=_cmmdcExtins(a,-b,m,n); n=-n; return d;}
}

bool diofant(int a,int b, int c, int &x0 , int &y0 , int &x1 , int &y1)
{ /// ax0 + by0 = c; ax1 +by1=0
int m, n, d=cmmdcExtins(a,b,m,n);
if(c%d!=0) return false;
int q=c/d;
x0=m*q; y0=n*q;
x1=-b/d; y1=a/d;
/// solutia generala x = x0 + x1*t, y = y0 + y1*t
return true;
}

int main ()
{ int a,b,c,x0 ,y0 ,x1 ,y1;
cout <<"a,b,c=";
cin >>a>>b>>c;

int raspuns=diofant(a,b,c,x0 ,y0 ,x1 ,y1);
if(raspuns=false ){ cout <<"ec nu are solutie "; return 0; }
cout <<"x="<<x0 <<showpos <<x1 <<"*t"<<noshowpos <<endl;
cout <<"y="<<y0 <<showpos <<y1 <<"*t"<<noshowpos <<endl;
return 0;
}

5 Probleme propuse

1. Fie a s , i b dou˘a numere naturale nenule, a ≤ b. G˘asit , i toate perechile de numere naturale
x, y astfel ˆıncˆat (x, y) = a s , i [x, y] = b.
ˆ
a
2. In planul xOy, prin cˆate puncte (x, y), x, y numere naturale, trece segmentul de dreapt˘
care unes , te punctele (0, 0) s , i (m, n), unde m, n sunt numere naturale?
3. Problema balant , ei. Avem o balant , ˘a s , i dou˘a tipuri de greut˘at , i a s , i b. Care este num˘arul
minim de greut˘at , i de care avem nevoie pentru a cˆant˘ari un produs cu greutatea c, dac˘a
acest lucru este posibil? (a, b, c sunt numere naturale nenule).

Bibliografie

[1] D.E. Knuth, Tratat de programarea calculatoarelor. Algoritmi Fundamentali, Editura Tehnic˘a,
1974.

[2] https://en.wikipedia.org/wiki/Binary GCD algorithm

[3] https://en.wikipedia.org/wiki/Greatest common divisor