exgcd

/* exgcd  __X * a + __Y * b = r = gcd(a, b)*/
int64 __X, __Y;
tuple<int64, int64, int64> exgcd(int64 a, int64 b) noexcept
{
    if (b == 0)
    {
        __X = 1;
        __Y = 0;
        return { __X, __Y, a };
    }
    int64 r = get<2>(exgcd(b, a % b));
    int64 tmp = __X;
    __X = __Y;
    __Y = tmp - a / b * __Y;
    return { __X, __Y, r };
}