扩展欧几里得算法

用途

当我们已知$(a,b)$

扩展欧几里得算法可以求出满足$p*a+q*b=GCD(a,b)$的$(p,q)$解集

$GCD(a,b)$表示$a,b$的最大公约数

前导知识

$GCD(a,b)=GCD(b,a\%b)$

$GCD(a,0)=0$

$a\%b=a-a/b*b$

推导过程

其实扩展欧几里得的推导过程挺自然的

$p*a+q*b$

$=GCD(a,b)$

$=GCD(b,a\%b)$

$=p*b+q*(a\%b)$

$=p*b+q*(a-a/b*b)$

$=p*b+q*a-q*a/b*b$

$=q*a+p*b-q*a/b*b$

$=q*a+(p-q*a/b)*b$

这样不断的递归下去

当$b==0$时

$p=1,q=0$

代码

注意：

我们在求$(p-q*a/b)$的时候需要用到上一层的$p$

但此时上一层$p$已经被赋值成了$q$

所以我们需要开一个中间变量来记录上一层的$p$

 1 int exgcd(int a,int b,int &x,int &y)
 2 {
 3     if(b==0)
 4     {
 5         x=1,y=0;
 6         return a;
 7     }
 8     int r=exgcd(b,a%b,x,y),tmp;
 9     tmp=x,x=y,y=tmp-a/b*y;
10     return r;
11 }

扩展欧几里得算法

原文：http://www.cnblogs.com/zwfymqz/p/7860554.html