Cod sursa(job #663722)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 18 ianuarie 2012 21:12:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<cstdio>
using namespace std;
struct sol
{
	int x,y;
}p;
int n,a,b,c,d,cmmdc(int x,int y ,sol& p);
void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	scanf("%d",&n);
}

void solve()
{
	for(;n--;)
	{
		scanf("%d%d%d",&a,&b,&c);
		d=cmmdc(a,b,p);p.x*=c/d;p.y*=c/d;
		c%d?printf("0 0\n"):printf("%d %d\n",p.x,p.y);
	}
}

int cmmdc(int x,int y,sol& p)
{
	int w;sol q;
	if(!y)
	{
		p.x=1;p.y=0;return x;
	}
	w=cmmdc(y,x%y,q);
	p.x=q.y;p.y=q.x-(x/y)*q.y;return w;
}