Se citesc a, b, c intregi. Sa se determine toate perechile intregi (x,y)

Se citesc a, b, c intregi. Sa se determine toate perechile intregi (x,y)  solutii ale ecuatiei ax+by=c.

Analiza problemei – elaborarea algoritmului;

Problema a fost data la olimpiada scolara de informatica. Ea pare la prima vedere imposibila.  Exista ecuatii, de exemplu: 3x+2y care are o infinitate de solutii . , (1,-1), (3,-4), (5,-7), (7,-10), . Cum ar putea fi afisata atunci  pe ecran o multime infinita de perechi ? Solutia este de a afisa aceasta multime printr-o descriere sintetica a ei (afisind formula care poate genera toate perechile ce o compun).

1. daca c=1 atunci exista (x₀,y₀) a.i. ax₀+by₀=1 doar daca [a,b]=1 ; restul solutiilor (x,y) au forma x=x₀+kb , y=y₀-ka, cu k intreg.

2. daca c>1 atunci exista solutiile (x₀,y₀) doar daca [a,b]|c; restul solutiilor se construiesc la fel;

prin [a,b] se intelege cmmdc(a,b)

Programul trebuie doar sa determine x₀ si y₀.

Program ax plus_by_egal_c;

Var a,b,c,x0,y0,y:integer;

BEGIN

Write('a,b,c=');Readln(a,b,c);

x0:=0;

For y:=0 to a do

If abs(c-b*y) mod a=0 then begin

y0:=y;x0:=(c-b*y) div a;break;

end;

If x0<>0 then Writeln('Sol. (x,y) ale ec. ',a,'x+',b,'y=',c,' sint (',x0,'+k*',b,',',y0,'-k*',a,')')

else Writeln('Nu exista solutii pentru ecuatia ',a,'x+',b,'y=',c);

END.

/*Varianta C de solutionare:

1. daca c=1 atunci exista (x0,y0) a.i. ax0+by0=1 doar daca cmmdc[a,b]=1 ;

restul solutiilor (x,y) au forma x=x0+kb y=y0-ka, cu k intreg.

2. daca c>1 atunci exista solutiile (x0,y0) doar daca cmmdc[a,b] | c;

restul solutiilor se construiesc la fel.

3. exista posibilitatea ca, pornind de la perechi (x0,y0) distincte, sa se

obtina solutii noi diferite (multimi infinite de perechi distincte).

4. toate solutiile (multimi infinite de perechi) pleaca de la o pereche

(x0,y0) aflata in dreptunghiul (-b,-a)x(b,a).

Un bun exemplu este ecuatia 18x+42y=6.*/

#include <stdio.h>

#include <math.h>

int a,b,c,x0=0,y0=0,y,k;

void main(void)

}

if(!x0 && !y0 && c)printf('Nu exista solutii pentru ecuatia %ix+%iy=%i',a,b,c);