Cod sursa(job #933078)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 29 martie 2013 16:33:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <iostream>
using namespace std;

ifstream f("euclid3.in"); ofstream g("euclid3.out");

int a, b, d, x, y, c, n;


/**
  * a and b are the numbers for gcd (a, b)
  * d is the greatest common divisor
  * x and y are a pair of numbers such that a*x + b*y = d
  * 
  * For Base Case (where a = d) we have trivial answer a*1 + b*0 = d
  * For Step we solve the following pair of equations
  * a*x + b*y     = d
  * b*x + (a%b)*y = d
  *
  * Common factor by a and b, then choose trivial sollutions.
  **/

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

int main(){
	f>>n;
	while (n--){
		f>>a>>b>>c;
		gcd(a, b, d, x, y);
		if (c%d) g<<"0 0\n";
		else g<<x*(c/d)<<' '<<y*(c/d)<<"\n";
	}
}