Cod sursa(job #1511431)

Utilizator HealeruDaniel Guramulta Healeru Data 26 octombrie 2015 19:11:48
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
// Algoritmul lui euclid extins.cpp : Defines the entry point for the console application.
//

///#include "stdafx.h"
#include <fstream>

using namespace std;

int gcd(int A, int B, int &X, int &Y) {
	if (B == 0) {
		X = 1;
		Y = 0;
		return A;
	}

	int x0, y0, D;
	D = gcd(B, A % B, x0, y0);
	X = y0;
	Y = x0 - (A / B) * y0;
	return D;
}

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

	int T;
	for (fin >> T; T; --T) {
		int A, B, C;
		fin >> A >> B >> C;
		int D, X, Y;
		D = gcd(A, B, X, Y);

		if (C % D)
			fout << "0 0" << "\n";
		else
			fout << X * (C / D) << ' ' << Y * (C / D) << "\n";
	}
	return 0;
}