Extended Euclidean algorithm.

extended_euclid.cpp

#include<tuple>

std::tuple<long long, long long, long long> _extendedEuclid(long long a, long long b, long long x, long long y, long long _x, long long _y) {
    if (a % b == 0) {
        return std::make_tuple(b, x, y);
    } else {
        long long q = a / b;
        return _extendedEuclid(b, a % b, _x - q * x, _y - q * y, x, y);
    }
}

std::tuple<long long, long long, long long> extendedEuclid(long long a, long long b) {
  // computes gcd(a, b) and x, y such that gcd(x, y) = ax + by
    if (b == 0) {
        return std::make_tuple(a, 1, 0);
    }
    return _extendedEuclid(a, b, 0, 1, 1, 0);
}