欧几里得和扩展欧几里得

int gcd(int a,int b){

　　return b==0? a : gcd(b,a%b);

}

LL extended_euclid(LL a,LL b,LL &x,LL &y){//扩张欧几里的算法

　　int d;

　　if(b==0){

　　　　 x=1; y=0;

　　　　 return a;

　　　　}

    d=extended_euclid(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}