Cod sursa(job #2481993)

Utilizator ionicaion ionica Data 27 octombrie 2019 17:46:28
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
using namespace std;

void euclid(long a,long b,long &u,long&v,long&d)
{
	long u1,u2,u3,v1,v2,v3,c,r;
	u1=1;u2=0;
	v1=0;v2=1;
	if(b==0)
    {
        u=1;
        v=0;
        d=a;
        return;
    }
	while(1)
	{
		c=a/b;
		r=a%b;
		if(r==0)break;
		u3=u1-c*u2;
		v3=v1-c*v2;

		u1=u2; u2=u3;
		v1=v2; v2=v3;

		a=b; b=r;
	}
	u=u2; v=v2; d=b;
}

int main()
{
	long a,b,c,d,u,v,n,j,sa,sb,x,y;
	ifstream f("euclid3.in");
	ofstream g("euclid3.out");
	f>>n;
	for(j=1;j<=n;j++)
	{f>>a>>b>>c;

	sa=sb=1;

	if(a<0){sa=-1;a=-a;}
	if(b<0){sb=-1;b=-b;}

	euclid(a,b,u,v,d);

	if(c%d!=0)g<<"0 0\n";
	else
	  {
	  u=u*(c/d); v=v*(c/d);
	  x=u*sa;
	  y=v*sb;
	  g<<x<<' '<<y<<'\n';
	  }
	}
}