【模板】各种欧几里得

原文地址

int gcd(int n,int m)//n>m
{
    //最大公约数
    int r;
    while(m)
    {
        r = n%m;
        n = m;
        m = r;
    }
    return n;
}

int kgcd(int a,int b)
{
    if(!a) return b;
    if(!b) return a;
    if(!(a&1) && !(b&1))
        return kgcd(a>>1,b>>1)<<1;
    else if(!(b&1)) return kgcd(a,b>>1);
    else if(!(a&1)) return kgcd(a>>1,b);
    else return kgcd(abs(a-b),min(a,b));
}

//扩展欧几里得
//求方程ax+by+c = 0有多少整数解
int extgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    int d = extgcd(b,a%b,x,y);
    int t = x;
    x=y;
    y=t-a/b*y;
    return d;
}