exgcd

void exgcd(int a, int b, int& d, int& x, int& y) {
    if(b) exgcd(b, a % b, d, y, x), y -= a / b * x;
    else d = a, x = 1, y = 0;
}