285484026

欧几里得算法与拓展欧几里得算法
欧几里德算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。算法描述:所以如果z如果是x,y的因子,则z...
扫描右侧二维码阅读全文
29
2018/11

欧几里得算法与拓展欧几里得算法

欧几里德算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。

算法描述:$$gcd(a,b) = gcd(b,a\%b) $$

运行实例:
输入a=15,b=10
$$gcd(a,b)=gcd(15,10)=gcd(10,5)=gcd(5,0)$$
对于一个非零数和0的最大公约数一定是非零数本身。于是$gcd(5,0)=5$

根据欧几里得算法得出我们在上述过程中最大公约数没有改变,于是得出gcd(15,10) = 5
同时可以证明在4.785lgN + 1.6723步之类,之内必定会有b会成为0,而b为0恰好就是递归的结束条件。就可以在之内寻找到a和b两个数的最大公约数,所以这是一个高效的寻找最大公约数的算法。
算法证明:
先介绍一个竖线这个符号,a|b 表示a整除b。
$$设z|x,z|y则z|(y-x)$$
$$a*z=x
b*z=y
(a-b)*z=(y-x)$$
所以如果z如果是x,y的因子,则z一定是y-x的公因子,所以可以发现换成数学表述形式就是

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

代码实现:

int gcd(int a,int b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

拓展欧几里得算法是用来在已知(a,b)时,求解一组(p,q),使得$a*p+b*q=c$
首先根据裴蜀定理可以证明解一定存在,这不是本文的重点,于是有兴趣的可以自行查阅资料。
定理1: 对于方程$a*p+b*q=c该方程等价于a*p\equiv c(mod\ b)$,该方程有整数解的充要条件是gcd(a,b)|c
我们再回顾上面欧几里得算法的实现过程
$\because gcd(a,b)=gcd(b,a\%b)$

p*a+q*b = gcd(a,b)
        = gcd(b,a%b) 
        = p*b+q*(a%b) 
        = p*b+(b-a/b*q)*b 

而同样类似于欧几里得算法最后根据一个非零数和0的最大公约数一定是非零数本身。
在拓展欧几里得算法中最后当b为0的时候就可以得出
p=1,q=0
a1+0b=gcd(a,0);
然后进行上述运算的逆运算就可以求解出想要的一组解p。
定理2:
方程的任意一组解可以表示为
$x=x_0 +b*t$

$y=y_0 -a*t$
且对于任意一组t都成立
于是为了得到最小的正整数x,我们进行一下操作

x=x%b;
while(x<0) x+=b;
#include <bits/stdc++.h>

using namespace std;
long long a,b,x,y;
long long ex_gcd(long long a,long long b,long long &x,long long &y)
{
    if(!b) {x=1;y=0;return a;}
    else {
        long long ans = ex_gcd(b,a%b,x,y);
        long long t=x;x=y;y=t-(a/b)*y;
        return ans;
    }
}
int main()
{
    while(scanf("%d %d",&a,&b) && a && b){
        long long ans = ex_gcd(a,b,x,y);
        x=x%b;
        while(x<0) x+=b;
        printf("%lld\n",x);
    }
    
    return 0;
} 
Last modification:January 7th, 2019 at 11:52 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment