Pagini recente » Cod sursa (job #115674) | Cod sursa (job #42163) | Cod sursa (job #2724404) | Cod sursa (job #942867) | Cod sursa (job #329653)
Cod sursa(job #329653)
#include <fstream>
#include <vector>
using namespace std;
struct entry {
int x,y,d;
entry(int xx,int yy,int dd) : x(xx), y(yy), d(dd) {}
};
entry ext(int A,int B) {
vector < entry > E;
E . push_back ( entry(1,0,A) ); E . push_back( entry(0,1,B) );
if(!A) return E[1]; if(!B) return E[0];
for(int t0 = A, t1 = B, i = 2; t0 % t1; ++i) {
int q=E[i-2].d / E[i-1].d,
xx = E[i-2].x - E[i-1].x * q,
yy = E[i-2].y - E[i-1].y * q,
dd = E[i-2].d % E[i-1].d;
t0 = E[i-1].d, t1 = dd;
E . push_back( entry(xx,yy,dd) );
}
return E.back();
}
int main() {
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int T;
fin >> T;
while(T--) {
int A,B,C;
fin >> A >> B >> C; // ax + by = c
entry t = ext(A,B);
if(C % t.d) fout << "0 0\n";
else { //fout << t .x << ' ' << t . y << ' ' << t. d << endl;
fout << t . x * C / t.d << ' ' << t . y * C / t.d << '\n'; }
}
return 0;
}