Cod sursa(job #1746230)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 22 august 2016 22:02:44
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int gcd(int a,int b)
{
	if (a%b==0)
		return b;
	else return gcd(b,a%b);
}
void Euclid(int a,int b,int &x,int &y)
{
	if(b==0)
		x=1,y=0;
	else 
	{
		int X,Y;
		Euclid(b,a%b,X,Y);
		x=Y,y=X-Y*(a/b);
	}
}
int T,A,B,C,D,x,y;
int main()
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
		scanf("%d%d%d",&A,&B,&C);
		D=gcd(A,B);
		if(C%D!=0)
			printf("0 0\n");
		else 
		{
			Euclid(A,B,x,y);
			printf("%d %d\n",x*C/D,y*C/D);
		}
	}
    return 0;
}