Cod sursa(job #1098880)

Utilizator casuneanu.andreiCasuneanu Andrei Dan casuneanu.andrei Data 5 februarie 2014 12:14:49
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
//
//  main.cpp
//  euclid3
//
//  Created by Casuneanu Andrei on 05/02/14.
//  Copyright (c) 2014 Casuneanu Andrei. All rights reserved.
//

#include <fstream>
#define IN "euclid3.in"
#define OUT "euclid3.out"
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

int euclid(int, int, int&, int&);
int t;

int main(int argc, const char * argv[])
{
	int i;
	int a, b, c, x, y;
	int xx;
	fin >>t;
	for (i=0; i<t; i++)
	{
		fin >>a>>b>>c;
		xx=euclid(a, b, x, y);
		if (c%xx) fout <<0<<' '<<0<<'\n';
		else fout <<x*(c/xx)<<' '<<y*(c/xx)<<'\n';
	}
	fout.close();
    return 0;
}

int euclid(int a, int b, int &x, int &y)
{
	if (!b) {x=1; y=0; return a;}
	int x0, y0, c;
	c=euclid(b, a%b, x0, y0);
	x=y0;
	y=x0-y0*(a/b);
	return c;
}