模板-gcd

GCD

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

EXGCD

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

模板-gcd

原文：https://www.cnblogs.com/Titordong/p/9609374.html