Cod sursa(job #967230)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int XA,XB,YA,YB;
int n,i,Xsol,Ysol;
int gcd(int a,int b) {
if (a==0) {
Xsol=XB;
Ysol=YB;
return b;
}
if (b==0) {
Xsol=XA;
Ysol=YA;
return a;
}
if (a>b) {
XA-=a/b*XB;
YA-=a/b*YB;
a%=b;
return gcd(a,b);
}
if (a<b) {
XB-=b/a*XA;
YB-=b/a*YA;
b%=a;
return gcd(a,b);
}
if (a==b) {
XA-=XB;
YA-=YB;
a=0;
return gcd(a,b);
}
}
int main() {
f>>n;
for(i=1;i<=n;++i){
int xx,yy,cc;
XA=1,YA=0,XB=0,YB=1;
f>>xx>>yy>>cc;
int GC=gcd(xx,yy);
int fact=cc/GC;
if (cc%GC!=0) g<<0<<" "<<0<<'\n';
else
g<<Xsol*fact<<" "<<Ysol*fact<<'\n';
}
f.close();
g.close();
return 0;
}