• Euclid: gcd(A,B) = gcd(B,A%B)
• Euclid mở rộng - phương trình Diophantine: Ax + By = GCD(A,B)

/// muoii
/// O(log(max(a,b)))

int diophante(int m,int n,int xm=1,int xn=0)
{
    if(n==0) return xm;
    return diophante(n,m%n,xn,xm-xn*(m/n));
}

void Diophante(int a,int b,int c,int &x,int &y) {
    if(c==0) return x=0,y=0,void();
    if(a==0) return x=0,y=c/b,void();
    if(b==0) return x=c/a,y=0,void();

    int d=__gcd(a,b);

    x = diophante(a,b);
    y = (c-a*x)/b;

    int k = c/d;
    x*=k;
    y*=k;

    return;
}
**/// ax + by = gcd(a,b) = d
/// (x0,y0) = (diophante(a,b),y0=(d-ax0)/b
/// (x,y) = (x0 + k*b/d,y0 - k*a/d)	(k is sig int)**