Pagini recente » Cod sursa (job #3126170) | Cod sursa (job #181141) | Cod sursa (job #1269802) | Cod sursa (job #17701) | Cod sursa (job #2710746)
#include <fstream>
using namespace std;
int a,b,c,d,q,x,y;
int cmmdc(int a, int b,int &x, int &y) {
if (b==0) {///ax+by=d
///ax=d
///x=d/a
///y=oricat
x=1;
y=0;
return a;
}
else {
int d=cmmdc(b,a%b,x,y);
int xa=x;
int ya=y;
int c=a/b;
///b*xa+(a%b)*ya=d
///inlocuim a%b cu a-b*c, unde c este catul impartirii a/b
///b*xa+(a-b*c)ya=d
///a*x+b*y=d ///vrem sa aflam x si y
///=> b*xa+(a-b*c)ya=a*x+b*y
///=> b*xa+a*ya-b*c*ya=a*x+b*y
///=> b(xa-c*ya-y)=a(x-ya)
///Una dintre solutii este
/// xa-c*ya-y=0 De unde rezulta y=xa-c*ya
/// x-ya=0 De unde rezulta x=ya
x=ya;
y=xa-c*ya;
return d;
}
}
int main() {
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
for (fin>>q;q--;) {
fin>>a>>b>>c;
d=cmmdc(a,b,x,y);
if (c%d==0) fout<<x*(c/d)<<" "<<y*(c/d)<<"\n";
else fout<<"0 0\n";
/// fout<<a<<" "<<"*"<<" "<<x<<" "<<"+"<<" "<<b<<" "<<"*"<<" "<<y<<" "<<"="<<" "<<d<<"\n";
}
return 0;
}