extendgcd

// ax+by = gcd(a,b) ->求解x,y 其中a,b不全为0，可以为负数
// 复杂度:O(log2a)
void extendgcd(ll a,ll b,long long &x,long long &y)
{
    if(a%b==0)
    {
        //到了终止条件
        x=0; y=1;
        return ;
    }
    extendgcd(b,a%b,x,y);
    long long tmpx;
    tmpx=y;
    y=x-(a/b)*y;
    x=tmpx;
}

//ax + by = gcd(a,b) 
//传入固定值a,b.放回 d=gcd(a,b), x , y
void MEuclid(int a,int b,int &d,int &x,int &y)
{
　　 if(b==0){d=a;x=1;y=0;return;}
 　　MEuclid(b,a%b,d,y,x);
　　 y-=x*(a/b);
}