Java教程

欧几里得(扩展)算法

本文主要是介绍欧几里得(扩展)算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

欧几里得算法

欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

证明
记a|d表示a可以整除d(d为a的倍数)
设d为a和b的公约数,即d|a,d|b。
a mod b = a-kb,显然d也为a mod b 的和b的公约数。

设d为a mod b和b的公约数,即d|b,d|(a mod b)
则有d|(a-kb),因为\(\frac{a}{d}-k\frac{b}{d}\)和\(\frac{b}{d}\)为整数,所以\(\frac{a}{d}\)必为整数,即d也为a和b的公约数。

综上,(a,b)与(b,a mod b)有相同的公约数,故其最大公约数也相等。

C++实现

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);//其实b比a大时也是对的
}

扩展欧几里得算法

扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。除了计算a、b两个整数的最大公约数,此算法还能找到整数x、y(其中一个很可能是负数)。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。

证明
我们先假设\(ax+by=gcd(a,b)\)①存在整数解,令\(r=a\%b\),
根据假设我们又可以得到个式子:
\(bx^{\prime}+ry^{\prime}=gcd(b,r)=gcd(a,b)\)存在整数解,将\(r=a-\lfloor \frac{a}{b} \rfloor b\)带入并整理
得:\(b(x^{\prime}-\lfloor \frac{a}{b} \rfloor y^{\prime})+ay^{\prime}=gcd(a,b)\)②
我们发现①②具有相同的形式,即①式的解可以从②式中获得:
\(x=y^{\prime},y=x^{\prime}-\lfloor \frac{a}{b} \rfloor y^{\prime}\)
这就是说只要我们找到②式的解,就能得到①式(上一层)的解。
根据相同的形式,从②式的原式我们又可以得到\(rx^{\prime\prime}+r^{\prime}y^{\prime\prime}=gcd(r,r^{\prime})=gcd(a,b),r^{\prime}=b\%r\)...
根据欧几里得,这个过程会有一个尽头:
\(dx+0y=gcd(a,b)\),其中\(d=gcd(a,b)\),为使等式成立,我们可以令\(x=1,y=0\)(当然也可以为其他值)
这就找到了一组可行解,在一层层倒退回去,就能得到原始方程的一组整数解。

C++实现

int exgcd(int a,int b,int &x,int &y){
    //x为a的解,y为b的解
    if(b==0){//到达尽头
        x=1,y=0;
        //y可赋任意整数值
        return a;//返回最大公因数
    }
    int d=exgcd(b,a%b,x,y);
    //此时的x,y为下一层的解
    int temp=y;
    y=x-a/b*y;//把y变成当前层解
    x=temp;//把x变成当前层解
    return d;
}
这篇关于欧几里得(扩展)算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!