Cod sursa(job #1220895)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 18 august 2014 21:29:32
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <cstdio>
#include <utility>
using namespace std;

int euclid(int a, int b){
	if(b == 0) return a;
	int c;
	while(b){
		c = a;
		a = b;
		b = c % b;
	}
	return a;
}

// d = gcd(a, b) = a * x + b * y  = d' = gcd(b, a % b) = b * x' + (a % b) * y'
// d = a * x + b * y = b * x' + (a - [a/b] * b) * y'
// d = a * x + b * y = a * y' + (x' - [a/b]*y') * b
// (d, x, y) = (d', y', x' - [a/b]*y') 

pair<int, int> euclid_ext(int a, int b){
	if(b == 0) return make_pair(1,0);
	pair<int, int> p;
	p = euclid_ext(b, a % b);
	return make_pair(p.second, p.first - a/b * p.second);
}

int main(){
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);
	int t, c, a, b, d;
	cin >> t;
	for(int i = 0; i < t; i++){
		cin >> a >> b >> c;
		if(c % (d = euclid(a,b)) == 0){
			pair<int, int> r = euclid_ext(a, b);
			cout << r.first * (c/d)  << " " << r.second * (c/d) << "\n";
		}else{
			cout << "0 0\n";
		}
	}
	return 0;
}