欧几里得算法

[任务]求两个数a,b的最大公约数 [例子]

/*利用递归*/
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
/*调用algorithm中的函数*/
__gcd(a,b);

扩展欧几里得

［任务］求出Ａ，Ｂ的最大公约数，且求出Ｘ，Ｙ满足ＡＸ＋ＢＹ＝ＧＣＤ（Ａ，Ｂ）

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

举例推导过程