Cod sursa(job #2449637)

Utilizator VirtanAlinaElenaVirtan Alina-Elena VirtanAlinaElena Data 20 august 2019 12:39:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <assert.h>

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

int main()
{
	FILE *fin = fopen("euclid3.in", "r");
	FILE *fout = fopen("euclid3.out", "w");
	int n, a, b, c, i, x, y;

	fscanf(fin, "%d", &n);
	for (i = 0; i < n; i++)
	{
		fscanf(fin, "%d %d %d", &a, &b, &c);
		assert(-1000000000 <= a && a <= 1000000000);
		assert(-1000000000 <= b && b <= 1000000000);
		assert( -2000000000 <= c && c <= 2000000000 && c != 0 );

		int copyC = c;
		if (c % euclid(a, b))
			fprintf(fout, "0 0\n");
		else
		{
			euclidExtins(a, b, &c, &x, &y);
			fprintf(fout, "%d %d\n", x * (copyC / c), y * (copyC / c)) ;
		}
	}
	return 0;
}