Pagini recente » Autentificare | Algoritmiada 2013 - Clasament Runda 1, Clasele 5-9 | Unlucky... | Monitorul de evaluare | Cod sursa (job #884076)
Cod sursa(job #884076)
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
freopen ("euclid3.in", "r", stdin);
freopen ("euclid3.out", "w", stdout);
int N, lastx, lasty, x, y, t, a, b, c, r, xt, yt;
cin >> N;
while(N--){
cin >> a >> b >> c;
/// I = lastx * a + lasty * b = a
/// and x * a + y * b = b
lastx = 1; lasty = 0; x = 0; y = 1;
while(b != 0) {
t = a / b;
r = a % b; a = b; b = r;
xt = x; yt = y;
//by reducing the two ecuations: multiply 2nd by t and substract from 1st
x = lastx - x * t;
y = lasty - y * t;
lastx = xt; lasty = yt;
}
if(!(c % a))
cout << (c / a) * lastx << " " << (c / a) * lasty << "\n";
else cout << "0 0\n";
}
return 0;
}