数论-扩展欧几里德算法模板

求解二元一次不定方程 mx + ny = gcd(m, n)

计算出 d = m mod n 和一组根 (x, y) .

void ex_gcd(int m, int n, int &x, int &y, int &d)
{
    if (n) { ex_gcd(n, m%n, y, x, d); y -= m/n*x; return; }
    d = m; x = 1; y = 0;
    return;
}