Cod sursa(job #386127)

Utilizator nandoLicker Nandor nando Data 24 ianuarie 2010 10:04:50
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <fstream>
#include <iostream>

using namespace std;

int solve(int a,int b,int& x,int& y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int x1,y1,d=solve(b,a%b,x1,y1);
	x=y1;
	y=x1-(a/b)*y1;
	return d;
}
int main(){
	int t,a,b,c,d,y,x;
	fstream fin("euclid3.in",ios::in);
	fstream fout("euclid3.out",ios::out);

	fin>>t;
	for(int i=0;i<t;i++){
		fin>>a>>b>>c;
		d=solve(a,b,x,y);
		if(c%d!=0){
			fout<<"0 0"<<endl;
		}else{
			fout<<x*c/d<<" "<<y*c/d<<endl;
		}
	}
	fin.close();
	fout.close();
}