Cod sursa(job #1237852)

Utilizator radudorosRadu Doros radudoros Data 4 octombrie 2014 21:58:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <iostream>
using namespace std;





long long int euclid(long long int a, long long int b)
{
	if (b == 0)
	{
		return a;
	}
	else
	{
		return euclid(b, b%a);
	}
}

int euclid2(int a,int b,  int &x, int &y)
{
	if (b == 0)
	{
		y = 0;
		x = 1;
		cout << x << ' ' << y << '\n';
		return a;
	}
	else
	{
		int x0, y0, d;
		d=euclid2(b,a%b,x0,y0);
		x = y0;
		y = x0 -(a / b)*y0;
		cout << x << ' ' << y <<'\n';
		return d;
	}
}



int main()
{
	int t;
	ifstream fin("euclid3.in");
	ofstream fout("euclid3.out");
	fin >> t;
	for (int i = 0; i < t; i++)
	{
		int a, b, c, x, y;
		fin >> a >> b >> c;
		int aux;
		
		aux =euclid2(a, b, x, y);

		if (c % aux)
			fout << "0 0" <<'\n';
		else
		{
			fout << x*(c / aux) << ' ' << y*(c / aux) << '\n';
		}
	}
}