扩展euclidean算法求乘法逆的代码实现

假设a和b是两个不为0的整数，以下代码用C/C++实现了求b模a的乘法逆的算法（返回-1时表示没有乘法逆）。

// find the inverse modulo a of b
int findInverse(int a, int b) {
    if (0 == a || 0 == b) {
        return -1;
    }

    if (a < 0) {
        a = -a;
    }
    if (b < 0) {
        b = -b;
    }

    int t0 = 0, t = 1, a0 = a, q = a / b, r = a - q * b;
    while (r > 0) {
        int temp = (t0 - q * t) % a0;
        if (temp < 0) {
            temp = temp + a0;
        }
        t0 = t;
        t = temp;
        a = b;
        b = r;
        q = a / b;
        r = a - q * b;
    }
    if (1 != b) {
        return -1;
    } else {
        return t;
    }
}