Cod sursa(job #790464)

Utilizator mihaiSimuSimu Mihai mihaiSimu Data 21 septembrie 2012 14:49:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>

long cmmdc(long a,long b){return b==0?a:cmmdc(b,a%b);}

void euclidExtended(long a,long b,long &x,long &y){
	if(b==0){
		x=1;y=0;return;
	}

	long x0,y0;
	euclidExtended(b,a%b,x0,y0);
	x=y0;y=x0-(a/b)*y0;
}

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