Pagini recente » Cod sursa (job #836608) | Cod sursa (job #914847) | Cod sursa (job #3134300) | Cod sursa (job #2156470) | Cod sursa (job #3183172)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");
int gcd(int a, int b){
while (b!=0){
int r=a%b;
a=b;
b=r;
}
return a;
}
int lcm(int a, int b){
return a*b/gcd(a, b);
}
int extgcd(int a, int b, int &ca1, int &cb1){
ca1=1, cb1=0;
int ca2=0, cb2=1, r, d;
while (b!=0){
r=a%b; d=a/b;
a=b; b=r;
ca1-=d*ca2; cb1-=d*cb2;
swap(ca1, ca2); swap(cb1, cb2);
}
return a;
}
int main(){
int n, a, b, c;
fin>>n;
while (n--){
fin>>a>>b>>c;
int x, y;
int GCD=extgcd(a, b, x, y);
if (c%GCD!=0)
fout<<"0 0\n";
else fout<<c/GCD*x<<' '<<c/GCD*y<<'\n';
}
}