Cod sursa(job #1521167)

Utilizator atitelAlexandru atitel Data 9 noiembrie 2015 23:06:13
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<fstream>

#define MAXIMUM(a,b) ((a)>(b))?(a):(b)
#define MINIMUM(a,b) ((a)<(b))?(a):(b)
#define ABS(a) ((a)<0)?(-a):(a)
#define SWAPD(a,b) {double c=a; a=b, b=c;}
using namespace std;

struct DiophantineEquation
{
	int a;
	int b;
	int c;
};
struct DiophantineSolution
{
	bool hasSolutions;
	int ax;
	int bx;
	int ay;
	int by;
};
struct Vector
{
	unsigned int length;
	int values[1000];
};

double getFCMMDC(double a, double b)
{
if(a==0.0) return 1.0;
while(b)
    if(a>b && b>0.0) a-=b;
    else b-=a;
return a;
};

DiophantineSolution solveDiophantineEquation(DiophantineEquation e)
{
DiophantineSolution s;
s.ax=0, s.ay=0, s.bx=0, s.by=0, s.hasSolutions=0;
double x0, y0=1, a0, b0, c0, cmmdc;
bool signa=0, signb=0, signc=0;
if(e.a<0) signa=1, e.a=-e.a;
if(e.b<0) signb=1, e.b=-e.b;
if(e.c<0) signc=1, e.c=-e.c;

cmmdc=getFCMMDC(e.a, e.b);
if((int)e.c%(int)cmmdc) return s;
a0=e.a/cmmdc, b0=e.b/cmmdc, c0=e.c/cmmdc;

Vector v; v.length=0;
int t1=(int)a0, t2=(int)b0, t3;
bool inversed=0;
if(t1<t2) {SWAPD(t1,t2); inversed=1;}
while(t2)   v.values[v.length++]=t1, t3=t1%t2, t1=t2, t2=t3;
while(--v.length) x0=y0, y0=(1-x0*v.values[v.length-1])/v.values[v.length];
if(inversed) SWAPD(x0,y0);


s.ax=x0*c0*((signa)?-1:1)*((signc)?-1:1), s.ay=y0*c0*((signb)?-1:1)*((signc)?-1:1);
s.bx=b0,s.by=a0*((s.ax<=0)?-1:1)*((s.ay<=0)?-1:1);
s.hasSolutions=1;
return s;
}

int main()
{
int n;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
f>>n;
for(int i=1;i<=n;++i)
    {
     DiophantineEquation e; f>>e.a>>e.b>>e.c;
     DiophantineSolution s; s=solveDiophantineEquation(e);
     if(!s.hasSolutions) g<<"0 0";
     else g<<s.ax+i*s.bx<<' '<<s.ay+i*s.by;
     g<<'\n';
    }
return 0;
}