Cod sursa(job #147336)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 2 martie 2008 20:08:51
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream.h>
#include <fstream.h>

#define IN "euclid3.in"
#define OUT "euclid3.out"

ifstream fin(IN);
ofstream fout(OUT);

long a,b,c,d;
long x,y,t;

void euclid(long a, long b, long *d, long *x, long *y);
void citire();

int main()
{
 int i;
    
 fin>>t;   
 
 for(i=1;i<=t;i++)
 {
  citire();
  euclid(a,b,&d,&x,&y);

  if(c%d!=0)
   fout<<0<<" "<<0<<endl;
  else
   fout<<x*(c/d)<<" "<<y*(c/d)<<endl;
 }
 fin.close();
 fout.close();
return 0;
}

void euclid(long a, long b, long *d, long *x, long *y)
{
 if(b==0)
 {
  *d=a;
  *x=1;
  *y=0;
 }
 else
 {
  long x0,y0;
  
  euclid(b,a%b,d,&x0,&y0);
  *x=y0;
  *y=x0-y0*(a/b);
 }
}

void citire()
{
 fin>>a>>b>>c;
}