Cod sursa(job #679933)

Utilizator RaduDoStochitoiu Radu RaduDo Data 13 februarie 2012 20:55:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<iostream>
#include<cstdio>
int n,i,a,b,c;
void euclid(int a,int b,int c)
{
	int x1=1,y1=0,x2=0,y2=1,aux;
	while(b!=0)
	{
		x1-=(a/b)*x2;
		y1-=(a/b)*y2;
		aux=x1;
		x1=x2;
		x2=aux;
		aux=y1;
		y1=y2;
		y2=aux;
		aux=b;
		b=a%b;
		a=aux;
	}
	if(c%a!=0)
		printf("0 0\n");
	else
		printf("%d %d\n",x1*(c/a),y1*(c/a));
}
int main()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		euclid(a,b,c);
	}
	return 0;
}