Cod sursa(job #344529)

Utilizator digital_phreakMolache Andrei digital_phreak Data 30 august 2009 14:49:23
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

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

int main() {
	int T,a,b,c,d,x,y;
	
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	
	scanf("%d",&T);
	for(;T;T--) {
		scanf("%d%d%d",&a,&b,&c);
		d = cmmdc(a,b,&x,&y);
		if (c % d != 0) {
			printf("%d %d\n",0,0);
		} else {
			printf("%d %d\n",x*(c/d),y*(c/d));
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}