Cod sursa(job #2272317)

Utilizator arosearose red arose Data 29 octombrie 2018 22:57:26
Problema Algoritmul lui Euclid extins Scor 40
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>

int gcd(int a,int b)
{
	while (b!=0)
	{
		int r = a%b;
		a = b;
		b = r;
	}
	return a;
}

void egcd(int a, int b, int *x1, int *x2)
{
	if (a==0)
	{
		*x1 = 0;
		*x2 = 1;
		return;
	}

	int _x1, _x2;
	egcd(b%a, a, &_x1, &_x2);
	//printf("%d %d", _x1, _x2);
	*x1 = _x2 - (b/a) * _x1;
	*x2 = _x1;

}

int main()
{
	FILE *inptr = fopen("euclid3.in", "r");
	FILE *outptr = fopen("euclid3.out", "w");

	int cases;
	fscanf(inptr,"%d",&cases);

	while(cases>0)
	{
		int a,b,c,x1=0,x2=0;
		fscanf(inptr,"%d %d %d", &a, &b, &c);
		
		int d = gcd(a,b);
		if (c%d==0) {
			egcd(a*c/d,b*c/d,&x1,&x2);
			fprintf(outptr,"%d %d\n", (c/d)*x1, (c/d)*x2);
		}
		else {
			fprintf(outptr,"0 0\n");
		}

		--cases;
	}

	return 0;
}