Pagini recente » Cod sursa (job #874583) | Cod sursa (job #2551176) | Cod sursa (job #113912) | Cod sursa (job #559145) | Cod sursa (job #572255)
Cod sursa(job #572255)
# include <algorithm>
using namespace std;
int T, a, b, c, s, t;
int euclid_extins (int a, int b, int &s, int &t) {
int r, c, s1, s2, t1, t2;
if ( !b ) {
s = 1;
t = 0;
return a;
}
s1 = 1; t1 = 0; s2 = 0; t2 = 1;
for ( r = a % b, c = a / b; r; ) {
s = s1 - s2 * c; s1 = s2; s2 = s;
t = t1 - t2 * c; t1 = t2; t2 = t;
a = b; b = r; r = a % b; c = a / b;
}
return b;
}
int main () {
freopen ( "euclid3.in", "rt", stdin );
freopen ( "euclid3.out", "wt", stdout );
scanf ( "%d", &T );
for ( ; T; --T ) {
scanf ( "%d%d%d", &a, &b, &c );
int d = euclid_extins ( a, b, s, t );
if ( c % d ) {
printf ( "0 0\n" );
}
else {
c /= d;
printf ( "%d %d\n", s * c, t * c );
}
}
return 0;
}