二进制GCD

inline int GCD(int x,int y){
    int i,j;
    if(x==0)return y;
    if(y==0)return x;
    for(j=0;0==(x&1);++i) x>>=1;   
    for(j=0;0==(y&1);++j) y>>=1;   
    if(j<i) i=j;
    while(1){
        if(x<y) x^=y,y^=x,x^=y;     
        if(0==(x-=y)) return y<<i;
        while(0==(x&1))x>>=1;
    }

EXGCD

int exgcd(int a,int b,int &x,int &y){
    if(b==0) {
        x=1,y=0;
        return a;       
    }
    int ret,tmp;
    ret=exgcd(b,a%b,y,x);
    tmp=x;x=y;y=tmp-a/b*y;
    return ret;
}

线性方程ax+by=c

bool Equation(int a,int b,int c,int &x,int &y){  ax+by=c
    int d=exgcd(a,b,x,y);
    if(c%d)return 0;
    x=c/d*x;
    y=c/d*y;
    return 1; 
}