Cod sursa(job #1553797)

Utilizator D4n13LMuntean Dan Iulian D4n13L Data 20 decembrie 2015 15:37:46
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.72 kb
#include<stdio.h>
#include<stdlib.h>


int cmmdc(a,b)
{
	int c;
	while(b != 0)
	{
		c= a%b;
		a= b;
		b= c;
	}
	return a;
}

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

}
int main(void)
{
	FILE* fin = fopen("euclid3.in","rt");
	FILE * fout = fopen("euclid3.out","wt");
	int T;
	fscanf(fin,"%d",&T);
	while(T > 0)
	{
		int a,b,c;
		fscanf(fin,"%d%d%d",&a,&b,&c);
		if( c % (cmmdc(a,b)) != 0)
			fprintf(fout,"%d %d\n",0,0);
		else
		{
			int d = cmmdc(a,b);
			int x = 0, y =  0;
			ExtEuclid(a,b,&x,&y);
			fprintf(fout,"%d %d\n",x*(c/d),y*(c/d));
		}
		T--;
	}
	fclose(fin);
	fclose(fout);
	return 0;
}