UVa 10104
From Algorithmist
- include<iostream>
- include<vector>
- 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";
}
