Cod sursa(job #2026728)

Utilizator sandruSandru Petru-Ionut sandru Data 24 septembrie 2017 22:20:17
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
//============================================================================
// Name        : euclid3.cpp
// Author      : Sandru Ionut
// Version     :
// Copyright   : Your copyright notice
// Description : Euclid extins
//============================================================================


#include <stdio.h>

struct triplet{
	int d;
	int x;
	int y;
};
triplet euclid(int a, int b)
{
    if (b == 0) {
    	triplet tr;
    	tr.d=a;
    	tr.x=1;
    	tr.y=0;
    	return tr;
    }
    else {
    	triplet tr=euclid(b,a%b);
    	triplet tr1;
    	tr1.d=tr.d;
    	tr1.x= tr.y;
		tr1.y=tr.x-(a/b)*tr.y;
		return tr1;
    }
}

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