Cod sursa(job #470676)

Utilizator vlad.maneaVlad Manea vlad.manea Data 15 iulie 2010 11:16:17
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
using namespace std;

void extended(long long a, long long b, long long &x, long long &y, long long &d) {

	long long T[3][2];

	T[0][0] = 1;
	T[0][1] = 0;
	T[1][0] = 0;
	T[1][1] = 1;

	long long r = a % b;
	long long q = a / b;
	long long i = 1;
	
	while (r > 0) {

		i = (i + 1) % 3;

		T[i][0] = T[(i + 1) % 3][0] - q * T[(i + 2) % 3][0];
		T[i][1] = T[(i + 1) % 3][1] - q * T[(i + 2) % 3][1];

		a = b;
		b = r;
		
		r = a % b;
		q = a / b;

	}

	d = b;
	x = T[i][0];
	y = T[i][1];

}

int main() {

	long long t, a, b, c, d, x, y;
	
	ifstream fin("euclid3.in");
	ofstream fout("euclid3.out");
	
	fin >> t;
	
	while(t--) {

		fin >> a >> b >> c;

		if (a > b) {
			extended(a, b, x, y, d);
		} else {
			extended(b, a, y, x, d);
		}

		if (c % d == 0) {
			fout << x * c / d << ' ' << y * c / d << '\n';
		} else {
			fout << 0 << ' ' << 0 << '\n';
		}

	}

	fin.close();
	fout.close();

	return 0;

}