Cod sursa(job #555388)

Utilizator Luca.LiviuLuca Liviu Luca.Liviu Data 15 martie 2011 14:23:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <stdio.h>
#include <stdlib.h>
long euclid (long a, long b, long &x, long &y) {
	if (b==0) {
		x=1;
		y=0;
		return a;
	
	
	}
	long d,x0,y0;
	d = euclid (b,a%b,x0,y0);
	x=y0;
	y=x0-(a/b)*y0;
	return d;
}
int main () {
	
	freopen ("euclid3.in","r",stdin);
	freopen ("euclid3.out","w",stdout);
	
	long t,i;
	scanf ("%ld",&t);
	
	for (i=1;i<=t;i++) {
		long a,b,c;
		scanf ("%ld %ld %ld",&a,&b,&c);
		long d,x,y;
		d=euclid(a,b,x,y);
		if ((c%d)!=0) printf ("0 0\n");
		else printf ("%ld %ld\n",x*(c/d),y*(c/d)); 
	}

	return 0;
}