Cod sursa(job #1103568)

Utilizator breta.ionutBreta Ionut breta.ionut Data 9 februarie 2014 19:50:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
using namespace std;

void euclidExt(int a, int b, int &cmmdc, int &x, int &y) {
	int x0, y0;

	if (b == 0) {
		cmmdc = a;
		x = 1;
		y = 0;
	}
	else {
		euclidExt(b, a % b, cmmdc, x0, y0);
		x = y0;
		y = x0 - (a / b) * y0;
	}
}

int main() {
	ifstream in("euclid3.in");
	ofstream out("euclid3.out");
	int i, n, a, b, c, cmmdc, x, y;

	in>>n;
	for (i = 0 ; i < n ; i ++) {
		in>>a>>b>>c;
		euclidExt(a, b, cmmdc, x, y);
		if (c % cmmdc == 0) {
			x = x * (c / cmmdc);
			y = y * (c / cmmdc);
			out<<x<<" "<<y<<"\n";
		}
		else {
			out<<0<<" "<<0<<"\n";
		}
	}
	in.close();
	out.close();

	return 0;
}