Cod sursa(job #1098859)

Utilizator casuneanu.andreiCasuneanu Andrei Dan casuneanu.andrei Data 5 februarie 2014 12:04:06
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 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);

void euclid(int, int, int&, int&);
int cmmdc(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=cmmdc(a, b);
		if (c%xx) fout <<0<<' '<<0<<'\n';
		else
		{
			euclid(a*(c/xx), b*(c/xx), x, y);
			fout <<x<<' '<<y<<'\n';
		}
	}
	fout.close();
    return 0;
}

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

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