Nu aveti permisiuni pentru a descarca fisierul grader_test1.in

Cod sursa(job #519449)

Utilizator lcodrutlucianLazar Codrut-Lucian lcodrutlucian Data 5 ianuarie 2011 16:45:01
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
using namespace std;

struct ExtCmmdc {
	int x0;
	int y0;
	int cmmdc;
};

ExtCmmdc extCmmdc(int a, int b) {
	int x = 0, y = 1;
	int lastx = 1, lasty = 0;
	int quotient, t;
	while (b != 0) {
		quotient = a / b;

		t = b;
		b = a % b;
		a = t;

		t = lastx;
		lastx = x;
		x = t - quotient * x;

		t = lasty;
		lasty = y;
		y = t - quotient * y;
	}
	ExtCmmdc rez;
	rez.x0 = lastx;
	rez.y0 = lasty;
	rez.cmmdc = a;
	return rez;
}

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

	int n;
	int a, b, c;

	in >> n;
	ExtCmmdc s;
	for(int i=0;i<n;i++){
		in >> a >> b >> c;
		s = extCmmdc(a, b);
		if (c%s.cmmdc!=0) {
			out << "0 0\n";
		} else {
			out << s.x0*c/s.cmmdc << " " << s.y0*c/s.cmmdc << "\n";
		}
	}

	in.close();
	out.close();
	return 0;
}