Cod sursa(job #1746232)

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

int gcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	else 
	{
		int X,Y,d;
		d=gcd(b,a%b,X,Y);
		x=Y,y=X-Y*(a/b);
		return d;
	}
}
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,x,y);
		if(C%D!=0)
			printf("0 0\n");
		else 
		{
			printf("%d %d\n",x*(C/D),y*(C/D));
		}
	}
    return 0;
}