Pagini recente » Cod sursa (job #1804027) | Cod sursa (job #3174277) | Cod sursa (job #1379163) | Cod sursa (job #2611815) | Cod sursa (job #329654)
Cod sursa(job #329654)
#include <fstream>
#include <vector>
using namespace std;
typedef long long ll;
struct entry {
ll x,y,d;
entry(ll xx,ll yy,ll dd) : x(xx), y(yy), d(dd) {}
};
entry ext(ll A,ll 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];
int i = 2;
for(ll t0 = A, t1 = B ; t0 % t1; ++i) {
ll 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--) {
ll 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;
}