modular_inverse.cc

/* a*x ≡ 1 (mod m) */
int inverse(int a, int m)
{
    int d = m, x = 0, s = 1, q, r, t;
    while (a != 0)
    {
        q = d / a, r = d % a;
        d = a, a = r;
        t = x - q * s, x = s, s = t;
    }
    if (d != 1) return -1;  // 沒有倒數、無法整除
    return (x + m) % m;
}