Cod sursa(job #359458)

Utilizator proflaurianPanaete Adrian proflaurian Data 26 octombrie 2009 21:56:59
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<stdio.h>
struct sol{int x,y;};
sol p;
int A,B,C,D,t,cmmdc(int u,int v,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",&t);
}
void solve()
{
	for(;t;t--)
	{
		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 u, int v,sol& P)
{
	int w;sol Q;
    if (!v){P.x=1;P.y=0;return u;}
    w=cmmdc(v,u%v,Q);P.x=Q.y;P.y=Q.x-(u/v)*Q.y;return w;
}