Cod sursa(job #1585165)

Utilizator sebii_cSebastian Claici sebii_c Data 30 ianuarie 2016 20:17:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>

using namespace std;

/**@brief Solves a * x + b * y = gcd(a, b)
 */
void euclid(int a, int b, int& x, int& y, int &d) {
    if (b == 0) {
	x = 1;
	y = 0;
	d = a;
    } else {
	int x0, y0;
	euclid(b, a % b, x0, y0, d);
	x = y0;
	y = x0 - (a / b) * y0;
    }
}

int main() {
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");

    int n; fin >> n;
    for (int i = 0; i < n; ++i) {
	int a, b, c;
	fin >> a >> b >> c;
	
	int x, y, d;
	euclid(a, b, x, y, d);
	if (c % d != 0) {
	    fout << 0 << " " << 0 << endl;
	} else {
	    fout << x * (c / d) << " " << y * (c / d) << endl;
	}
    }

    return 0;
}