Cod sursa(job #595847)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 14 iunie 2011 16:57:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include<stdio.h>

int t,a,b,c;

void euclid(int a,int b,int &x,int &y,int &d) {
	if(b==0) {
		d=a;
		x=1;
		y=0;
		return;
	}
	int q=a/b,xx=0,yy=0;
	euclid(b,a%b,xx,yy,d);
	x=yy;
	y=xx-q*yy;
}

int main() {
	int i,x=0,y=0,d=0;
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	scanf("%d",&t);
	for(i=1;i<=t;++i) {
		scanf("%d%d%d",&a,&b,&c);
		euclid(a,b,x,y,d);
		if(c%d==0) {
			x*=c/d;
			y*=c/d;
		}
		else {
			printf("0 0\n");
			continue;
		}
		printf("%d %d\n",x,y);
	}
	return 0;
}