（扩展）欧几里得算法模板

LL (LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

///求解二元一次方程：ax + by = gcd(a,b)
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;} ///不妨假设 y=0，则x=1
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y; ///x'=y,y'=x-a/b*y
    return res; ///返回上一个状态
}