Cod sursa(job #1199517)

Utilizator silidragosSilion Dragos silidragos Data 19 iunie 2014 16:31:20
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<iostream>
#include<fstream>
using namespace std;

struct dub{
	long long x;
	long long y;
};

long long gcd(long long a, long long b, long long &x, long long&y){
	long long r;
	dub V, Va,Vn;
	Va.x = V.y = 1;
	Va.y = V.x = 0;
	while (b != 0){
		r = a%b;
		if (r != 0){
			Vn.x = Va.x - (a / b)*V.x;
			Vn.y = Va.y - (a / b)*V.y;
			Va = V;
			V = Vn;
		}
		a = b;
		b = r;
		
	}
	x = V.x;
	y = V.y;
	return a;
	 

}



int main(){
	ifstream f("euclid3.in", ios::in);//Change the name
	ofstream g("euclid3.out", ios::out);//Change the name

	int T;
	long long a, b, c;
	f >> T;

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



	f.close();
	g.close();
	return 0;
}