#include <iostream>
using namespace std;
int main()
{ const long long a=12345,  b=678900;
  long long q,a1,x1,y1,a2,x2,y2,a3,x3,y3;
  if (a==0) {a2=b;  x2=0;  y2=1;} else
  if (b==0) {a2=a;  x2=1;  y2=0;} else
  { a1=a;  x1=1;  y1=0;
    a2=b;  x2=0;  y2=1;
    do { q=a1/a2;  x3=x1-q*x2;
        a3=a1%a2;  y3=y1-q*y2;
        a1=a2;  x1=x2;  y1=y2;
        a2=a3;  x2=x3;  y2=y3;
       }
    while (a3!=0);
  }
  cout<<"GCD ("<<a<<", "<<b<<") = "<<a1<<" = "<<x1<<" * "<<a<<" ";
  if (y1>=0) cout<<"+ ";
  cout<<y1<<" * "<<b;
  return 0;
}