Extended Euclid Algorithm | Aizu Online Judge http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E&lang=jp

NTL_1_E.cpp

#include <iostream>

using namespace std;

int extgcd(int a, int b, int *x, int *y) {
  int d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    *y -= (a / b) * *x;
  }
  else {
    *x = 1; *y = 0;
  }
  return d;
}

int main(){
  int a, b, x, y;
  cin >> a >> b;
  extgcd(a, b, &x, &y);
  cout << x << " " << y << endl;
  return 0;
}