Cod sursa(job #1537758)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 27 noiembrie 2015 22:04:32
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <cstdio>

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

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