算法扩展：欧几里得算法详解

int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}

int egcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int nx, ny;
    // b*nx + a%b*ny = q
    int q = egcd(b, a % b, nx, ny);
    //   a*x + b*y
    // = a*ny + b*nx - b*(a/b)*ny
    // = b*nx + (a - b*(a/b))*ny
    // = b*nx + a%b*ny
    // = q
    x = ny;
    y = nx - (a / b) * ny;
    return q;
}

/**
 * @returns (x % b + b) % b where a*x + by = gcd(a, b)
*/
int mod_inv(int a, int b) {
    int x, y;
    egcd(a, b, x, y);
    return (x % b + b) % b; // possible that x < 0
}