Cod sursa(job #1202638)

Utilizator Kerriganamihut Kerrigan Data 28 iunie 2014 19:00:34
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
/******************************************************************************************
*           .--.																		  *
* ::\`--._,'.::.`._.--'/::			@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;
}