Pagini recente » Cod sursa (job #3175816) | Cod sursa (job #2856252) | Cod sursa (job #2064660) | Cod sursa (job #1979123) | Cod sursa (job #2386521)
#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;
if(x == 0){
if(rez %y==0){
fout << "0 " << rez/y << '\n';
}
else
fout << "0 0\n";
continue;
}
if(y==0){
if(rez %x==0){
fout << rez/x << " 0\n";
}
else
fout << "0 0\n";
continue;
}
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;
rest = v1%v2;
if(rest==0){
sol1 = b.x;
sol2 = b.y;
return;
}
cat = v1/v2;
c.x = a.x - cat*b.x;
c.y = a.y - cat*b.y;
euclidExtins(v2, rest, b, c);
}