Pagini recente » Cod sursa (job #1742916) | Cod sursa (job #548978) | Cod sursa (job #269163) | Cod sursa (job #2597470) | Cod sursa (job #1202638)
/******************************************************************************************
* .--. *
* ::\`--._,'.::.`._.--'/:: @author Ana M. Mihut @course InfoArena EduArchive *
* ::::. ` __::__ ' .::::: @alias LT-Kerrigan @date 28.06.2014 *
* ::::::-:.`'..`'.:-:::::: @link http://infoarena.ro/problema/euclid3 *
* ::::::::\ `--' /:::::::: @detail Extended Euclidean Algorithm *
* *
*******************************************************************************************/
#include <iostream>
#include <fstream>
long long a, b, c, d, x, y;
long long gcd(long long a, long long b){
return (b != 0) ? gcd(b, a%b) : a;
}
void ExtendedEuclid(long long a, long long b, long long &x, long long &y){
if (b == 0) {
x = 1;
y = 0;
}
else {
long long x0, y0;
ExtendedEuclid(b, a % b, x0, y0);
x = y0;
y = x0 - a/b * y0;
}
}
int main(){
int T;
FILE *in = freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
fscanf(in, "%d", &T);
for (int i = 1; i <= T; i++){
std::cin >> a >> b >> c;
d = gcd(a,b);
if (c%d != 0)
std::cout <<"0 0 \n";
else {
ExtendedEuclid(a, b, x, y);
std::cout << c / d *x << ' ' << c / d *y << "\n";
}
}
return 0;
}