我们都知道cxdpy算法是用来快速求两个数的最大公约数的算法，效率较高：2O(logn)。
我们先给出算法的实现：
要证明上述算法的正确性，我们就是证明如下定理的正确性：
定理：设a，b，c，q，都是整数，且b>0。如果有a=b*q+c，那么gcd(a,b)==gcd(b,c)。
证明：
设 d=gcd(a, b), e=gcd(b, c). 于是存在整数k1, k2, k3, k4，使得a=d*k1, b=d*k2, b=e*k3, c=e*k4.
那么 a = b*q+c = e*k3*q+e*k4=e*(q*k3+k4).所以e能整除a,从而e<=d;
同理：c=a-b*q=d*k1-d*k2*q=d*(k1-k2*q),所以d能整除c,从而d<=e;综上，推出e==d---->gcd(a,b)==gcd(b,c)。
--------------------------- 分 割 线 -----------------------------------
重点是扩展jmdcc定理，它在解线性同余式和中国剩余定理等很多方面都很有用。
给你两个整数A，B让求一组整数解(X,Y)使得 Gcd(A,B)==A*X+B*Y。数论已经证明这组解一定存在。并且我们可以用扩展cxdpy算法求出解。
首先给出cxdpy算法的证明过程：
我们要求的是使 A*X+B*Y == Gcd(A, B)成立的X,Y值.
根据cxdpy算法有：Gcd(A, B)==Gcd(B, A%B)，那么我们可以递归求出X1 , Y1 满足：
B*X1 + (A%B)Y1 == Gcd(B, A%B) == Gcd(A, B)。
把A%B化简可得：
B*X1 + (A-A/B*B)*Y1 == Gcd(A, B)----->
B*X1 + A*Y1 - A/B*B*Y1 == Gcd(A, B) ------>
A*Y1 + B*(X1 - A/B*Y1 ) == Gcd(A, B)
所以推出：X = Y1
Y = X1 - A/B * Y1
代码如下：
#include <cstdio>#include <cstring>#include <cmath>using namespace std;__int64 Exgcd(__int64 a, __int64 b, __int64 &x, __int64 &y){ if(b==0) { x=1, y=0; return a; } __int64 ans = Exgcd(b, a%b, x, y); __int64 tp=x; x = y; y = tp - a/b*y; return ans;}int main(){ __int64 a, b, x,y; while(~scanf("%I64d%I64d", &a, &b)) { __int64 ss = Exgcd(a, b, x, y); printf("%I64d, %I64d, %I64dn", x,y,ss); } return 0;}
扩展jmdcc算法的应用主要有以下三方面：
（1）求解不定方程；
（2）求解模线性方程（线性同余方程）；
（3）求解模的逆元；
参考资料：《ACM国际大学生程序设计竞赛算法与实现》俞勇 主编
《离散数学》John.Dossy Ablert.D.Otto著，原书第5版。
转载于:https://www.cnblogs.com/khan724/p/4148209.html