Pagini recente » Cod sursa (job #3252819) | Cod sursa (job #2038578) | Cod sursa (job #2977248) | Cod sursa (job #1537274) | Cod sursa (job #2722561)
#include <fstream>
using namespace std;
int q,a,b,c,x,y;
int euclid (int a, int b, int&x, int &y) {
if (b==0) {
///a*x+b*y=d
///a*x=d
///x=d/a
///x=a/a
///x=1, y=orice
x=1,y=0;
return a;
}
else {
int xa,ya;
int d=euclid(b,a%b,xa,ya);
///b*xa+(a%b)*ya=d
///a%b=a/b*c
///b*xa+(a-b*c)*ya=d
///a*x+b*y=d
///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(ya-x)=0
///ya-x=0 =>x=ya
///xa-c*ya-y=0 =>y=xa-c*ya
int c=a/b;
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;
///a*x+b*y=c
int d=euclid(a,b,x,y);
if (c%d==0) {
fout<<x*c/d<<" "<<y*c/d<<"\n";
}
else {
fout<<"0 0\n";
}
}
return 0;
}