Cod sursa(job #500355)

Utilizator cosmyoPaunel Cosmin cosmyo Data 11 noiembrie 2010 22:27:24
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<cstdio>
#include<cassert>
using namespace std;
int a,b,c,t,x,y,d;

const int inf=2000000000;

int euclid(int a,int b,int &x,int &y)
{
	if(b==0)
	{x=1;
	 y=0;
	 return a;
	}

	int x0,y0,d;

	d=euclid(b,a%b,x0,y0);

	x=y0;
	y=x0-(a/b)*y0;

	return d;

}

int main()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
		
	    scanf("%d",&t);
		
			for(;t;--t)
			{scanf("%d%d%d",&a,&b,&c);
             
				assert(-inf<=a&&a<=inf);
				assert(-inf<=b&&b<=inf);
				assert(-inf<=c&&c<=inf);

				d=euclid(a,b,x,y);

					if(c%d)
						printf("%d %d\n",0,0);
					else
						printf("%d %d\n",(c/d)*x,(c/d)*y);
			}

	 fclose(stdin);
	 fclose(stdout);
 return 0;
}