Cod sursa(job #523411)

Utilizator kitzTimofte Bogdan kitz Data 17 ianuarie 2011 22:25:30
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream.h>
ifstream f("euclid3.in");
ofstream g("euclid3.out");
long a, b, c;
short n;
int x, y, xp, yp;
long euclid(long a, long b, int &xx, int &yy)
{int r, x1, x2, y1, y2, q;
 if(b==0){xx=1;yy=0; return a;}
 else {r=a%b; q=a/b;
       x1=1; x2=0; y1=0; y2=1;
       while(r) { xx=x1-x2*q; x1=x2; x2=xx;
	              yy=y1-y2*q; y1=y2; y2=yy; 
	              a=b; b=r; r=a%b; q=a/b;
				}
	   return b;
      }
}
int main()
{f>>n;
 for(int i=1;i<=n;i++)
 {f>>a>>b>>c;
  x=0; y=0; xp=0;yp=0;
  long d=euclid(a, b, x, y);
  if(c%d!=0) g<<0<<" "<<0<<"\n";
  else {long e=c/d;
        x*=e;
        y*=e; 
        g<<x<<" "<<y<<"\n";
       }
 }
 g.close();
 f.close();
 return 0;
}