UVa 10104

From Algorithmist
Jump to navigation Jump to search
  1. include<iostream>
  2. include<vector>
  3. include<conio.h>

using namespace std;

/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/

class Euclid {

public:

 long long int get_a() const { return a; }
 long long int get_b() const { return b; }
 std::istream& read_AB(std::istream&);
 long long int find_gcd(long long int,long long int);
 long long int calculate_XY();
 void output();
       

private:

 long long int a,b;
 long long int d,x,y;
 std::vector<long long int> XX,YY,DD;

};


/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/

int main() {

 class Euclid ec;
 char ch;

 while(ec.read_AB(cin))
   {
             
     ec.find_gcd(ec.get_a(),ec.get_b());
     ec.calculate_XY();
           
   }
   
   ec.output();  
 
 getch();
   

}


/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/


istream& Euclid::read_AB(istream& in) {

in>>a>>b; }

long long int Euclid::find_gcd(long long int a,long long int b)

   { 
    
       if(b==0)
         d= a; 
    
       else
         d=find_gcd(b,a%b);
   }

long long int Euclid::calculate_XY()

   {
   
       long long int x1 = 0, y1 = 1;
       long long int prevx = 1, prevy = 0;
       long long int A=a;
       long long int B=b;
   
       while (b!=0)
       {


             long long int holdValue=b;
             long long int quotient=a/b;
             b=a%b;
             a=holdValue;     

             holdValue=x1;
             x1=prevx-quotient*x1;
             prevx=holdValue;
             holdValue=y1;
             y1=prevy-quotient*y1;
             prevy=holdValue;
       
       
     


     }
     
     if(prevy<prevx)
     {
             x=prevx-B/d;
             y=prevy+A/d;
     }
     
     else
     {
             x=prevx;

y=prevy;

     }
     
     XX.push_back(x);
     YY.push_back(y);
     DD.push_back(d);
     
   

}

void Euclid::output() {

    for(vector<long long int>::size_type i=0;i<XX.size();i++)
 cout<<"\n"<<XX[i]<<" "<<YY[i]<<" "<<DD[i]<<"\n";

}