Cod sursa(job #364582)

Utilizator andreitheo87Teodorescu Andrei-Marius andreitheo87 Data 16 noiembrie 2009 14:22:31
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<iostream>
using  namespace std;
int mygcd(int a,int b,int& x,int& y)
{
	if(b==0){
	    x = 1; y = 0;
        return a;
	}else{
	    int x0,y0, gc;
	    gc = mygcd(b , a%b , x0 , y0);
	    x = y0;
	    y = x0 - (a/b)*y0;
        return gc;
	}
}
int main()
{
	freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
	int nrt;
	scanf("%d",&nrt);
	for(int test = 0; test<nrt; test++)
	{
		int a,b,c,x,y;
		scanf("%d %d %d",&a,&b,&c);
		int gc=mygcd(a,b,x,y);
		if( c % gc != 0 ) printf("0 0\n");
		else{
                c /= gc;
                x *= c; y*=c;
                printf("%d %d\n",x,y);
		}
	}
	return 0;
}