Pagini recente » Cod sursa (job #405441) | Cod sursa (job #1998647) | Cod sursa (job #1550811) | Cod sursa (job #74054) | Cod sursa (job #2386508)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
struct config{
int x, y;
};
config init1, init2, a;
int x, y, rez, cmmdc, sol1, sol2, q, i;
int euclid(int, int);
void euclidExtins(int, int, config, config);
int main(){
fin >> q;
for(i=1; i<=q; ++i){
fin >> x >> y >> rez;
cmmdc = euclid(x, y);
init1.x = 1; init1.y = 0;
init2.y = 0; init2.y = 1;
euclidExtins(x, y, init1, init2);
if(sol1*(rez/cmmdc) * x + sol2*(rez/cmmdc) * y == rez)
fout << sol1*(rez/cmmdc) << ' ' << sol2*(rez/cmmdc) << '\n';
else
fout << "0 0\n";
}
return 0;
}
int euclid(int x, int y){
if(y == 0)
return x;
return euclid(y, x%y);
}
void euclidExtins(int v1, int v2, config a, config b){
int cat, rest;
config c;
cat = v1/v2; rest = v1%v2;
if(rest==0){
sol1 = b.x;
sol2 = b.y;
return;
}
c.x = a.x - cat*b.x;
c.y = a.y - cat*b.y;
euclidExtins(v2, rest, b, c);
}