gcd

gcd.cpp

// public domain
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
  int a, b;
  cin >> a >> b;
  int A = a;
  int B = b;
  
  vector<int> v;
  while(a % b != 0)
  {
    int x = a / b;
    v.push_back(x);
    x = a % b;
    a = b;
    b = x;
    
  }
  
  int g = b;
  int r = 1;
  int s = -v.back(); v.pop_back();
  while(!v.empty())
  {
    int x = v.back(); v.pop_back();
    int ps = s;
    s = r - s * x;
    r = ps;
  }
  
  cout << g << " = " << r << "*" << A << ((s>=0)?" +":"") << s << "*" << B << endl;
}