Cod sursa(job #626985)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 28 octombrie 2011 18:56:57
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include<iostream>

using namespace std;

int cmmdc(int a,int b)
{
	if (b == 0) return a;
	return cmmdc(b, a % b);
}

int c;
void diofant(int a, int b, int &x, int &y)
{
	if (a == 1 && b == 1) {x = c; y =0;} 
	else
	{
		int x1, y1;
	
		diofant (b, a-b, x1, y1);
		x = y1;
		y = x1 - y1;
	}
}


int main()
{
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);

	int T;
	scanf("%d", &T);
	
	for (; T <= 100; T--)
	{
		int a, b;
		scanf("%d %d %d", &a, &b, &c);
		
		int d = cmmdc(a, cmmdc(b, c));
		a /= d;
		b /= d;
		c /= d;
		
		int x, y; 
		
		if(abs(a) < abs(b)) diofant(abs(b), abs(a), y, x);			
		else diofant(abs(a), abs(b), x, y);
		
		if(a < 0) x *= -1;
		if(b < 0) y *= -1;
		
		printf("%d %d", x, y);
	}
	
	return 0;
}