<更新提示> <第一次更新> <正文> Euclid算法(gcd) 在学习扩展欧几里得算法之前，当然要复习一下欧几里得算法啦。 众所周知，欧几里得算法又称gcd算法，辗转相除法，可以在O(log2b)时间内求解(a,b)(a，b的最大公约数)。 其核心内容可以陈述为:(a,b)=(b,a%b)，然后反复迭代该式缩小a,b规模，直到b=0，得到a为最大公约数。 证明 设两数为a b(b＜a)，求它们最大公约数的步骤如下：用b除a，即a/b=q…..r，得a＝bq＋r(0≤r＜b，即为余数，q是这个除法的商)。若r=0，则b是a和b的最大公约数，a，b存在倍数关系。若r≠0,则继续考虑。 首先，应该明白的一点是任何 a 和 b 的公约数都是 r 的公约数。要想证明这一点，就要考虑把 r 写成 r=a−bq。现在，如果 a 和 b 有一个公约数 d，而且设 a=sd,b=td， 那么 r=sd−tdq=(s−tq)d。因为这个式子中，所有的数(包括 s−tq)都为整数，所以 r 可以被 d 整除。 对于所有的 d 的值，这都是正确的。所以 a 和 b 的最大公约数也是 b(因为b using namespace std; inline int Extended_Euclid(int a,int &x,int b,int &y,int c) { if(b==0){x=c/a,y=0;return a;} else { int p=Extended_Euclid(b,x,a%b,y,c); int x_=x,y_=y; x=y_; y=x_-a/b*y_; return p; } } int main(void) { int a,b,c; scanf("%d%d%d",&a,&b,&c); int p,x,y; p=Extended_Euclid(a,x,b,y,c); printf("(%d,%d)=%d\n",a,b,p); printf("x=%d,y=%d\n",x,y); }https://www.cnblogs.com/Parsnip/p/10115948.html