Cod sursa(job #473944)

Utilizator aladinaladin aladinn aladin Data 1 august 2010 20:14:33
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.46 kb
#include <cstdio>
int t,a,b,c;

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);
		int d=a,i=b,r=a%b,nr=0,v[10000];
		while (r!=0)
			++nr,v[nr]=d/i,d=i,i=r,r=d%i;
		if (c%i) printf("0 0\n"); else
		{
			int x=0,y=1;			c/=i;
			for (i=nr;i>0;--i)
				d=x,x=y,y=d-v[i]*y;
			printf("%d %d\n",x*c,y*c);
				
		}	
				
	}
 return 0;}