Cod sursa(job #1297589)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 22 decembrie 2014 09:40:18
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.46 kb
#include <fstream>

void extins(int a, int b, int *d, int *x, int *y){
	if(b==0){
		*d=a;
		*x=1;
		*y=0;
	}
	else{
		int x0,y0;
		extins(b,a%b,d,&x0,&y0);
		*x=y0;
		*y=x0-(a/b)*y0;
	}

}

int main(){
    std::ifstream fin("euclid3.in");
    std::ofstream fout("euclid3.out");

    unsigned T;
    fin>>T;

    for(;T>0;--T){
		int a,b,c;
		fin>>a>>b>>c;

		int d,x,y;
		extins(a,b,&d,&x,&y);

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

}