欧几里得(扩展)算法

欧几里得算法

欧几里得算法又称辗转相除法,是指用于计算两个非负整数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;
}

推荐这些文章:

最大公约数及扩展欧几里得算法

定理一
\(a\ mod\ b = a - b * \lfloor \frac {a}{b} \rfloor\)
证明:
\[\because a = k * b + r
\\\therefore \lfloor \frac{a}{b} \rfloor = k
\\即 a \ mod \ b = r, a - b * \lfloor \frac{a}{b} \rfloor
\]定理二 辗转相除法
\(gcd(a,b) = gcd(b, a\ mod\ b)\)
证明:
\[设d = gcd(a, b)
\\则有d|a,\ d|b
\\令c = a\ mod\ b
\\\because a =...

【墨鳌】【数论小结 01】【乘法逆元】【扩展欧几里得】

数论小结
1. 扩展欧几里得
首先,根据辗转相除法,不难有:
\[\gcd(a,b)=\gcd(b,a\%b)
\]关于扩展欧几里得算法,是解决线性方程:\(ax+by=c\) 当且仅当,\(\gcd(a,b)|c\) 有解
又因为,\(x,y\in\Z\),所以问题可以转化为,解线性方程:\(ax+by=\gcd(a,b)\) 这就是扩展欧几里得算法的初始条件
假设,我们有方程的一组解 \(x_0,y_0\), 则:
\[ax_0+by_0=\gcd(a,b)=\gcd(b,a\%b)\qquad(1)
\]于是,构造新的线性方程与其解 \(x_1,y_1\),满足:
\[bx_1+(a\...

最大公约数与最小公倍数_c/c++

gcd:greatest common divisor,最大公约数
 
欧几里得算法,也就是辗转相除法。公式:gcd(a, b) = gcd(b, a % b)
 
推论:gcd(b, a) == gcd(b, a-k*b)
 

1 //gcd模板
6 int gcd(int x, int y) {
7 return !x ? y : gcd(y % x, x);
8 }

推论:
  最小公倍数:
 
  x, y的最小公倍数为:x * y / gcd(x, y)
 

...

【算法】最大公约数和最小公倍数求解

1.概念:

最大公约数(Greatest Common Divisor,gcd)是数学词汇,指能够整除多个整数的最大正整数。而多个整数不能都为零。例如8和12的最大公因数为4。[维基百科]

最小公倍数(Least Common Multiple,lcm)是数论中的一个概念。若有一个数X,可以被另外两个数A、B整除,且X大于(或等于)A和B,则X为A和B的公倍数。所有正的公倍数中,最小的公倍数叫做最小公倍数。[维基百科]

2.求解最大公约数效率最高的当属辗转相除法(也叫欧几里得法)
而求最小公倍数可以利用公式lcm = m*n/gcd,这样最便捷。

代码示例如下

// 最大公约...

扩展欧几里得

概念
扩展欧几里得算法(\(\texttt{exgcd}\)) 是一种可以求出关于 \(x, y\) 的方程 \(ax + by = \gcd(a, b)\) 的通解的算法。
不妨设 \(a > b\),则 \(\tt exgcd\) 的时间复杂度为 \(O(logb)\)
思想
\(\texttt{exgcd}\) 的实现求出的是原方程的一组整数特解 \(x, y.\)
显然当 \(b = 0\) 时原方程有一组特解 \(x = 1, y = 0\)
当 \(b \neq 0\) 时,设方程 \(bx + (a \bmod b)y = \gcd(b, a \bmod b)\) 有一组...

C++求最大公约数(欧几里得算法)

C++中求最大公约数主要采用欧几里得算法,欧几里得算法的核心其实是\(gcd(a, b) = gcd(b, a\ mod\ b)\)下面进行证明

对\(a\ mod \ b\)进行变换
\[\begin{align*}
a\ mod\ b &= a - \left \lfloor \frac{a}{b} \right \rfloor \times b\\
&=a - c\times b
\end{align*}
\]

证明对于\(a\)和\(b\)的任意公约数\(k\),都是\(b\)和\(a\ mod\ b\)的公约数
是\(b\)的公约数,同...

扩展欧几里德算法

扩展欧几里德算法已经搞了好几天了,今天终于看明白,小做总结。
讲扩展欧几里得算法之前,先讲欧几里得算法和贝祖定理。
欧几里得算法
欧几里得算法就是辗转相除法,即gcd(a,b)=gcd(b,a%b)。
简单证明一下:
r=gcd(a,b),a=nr,b=mr。
a%b=(n-n/m*m)r。
因为gcd(n,m)=1。
设w=n/m。
则gcd(m,n-w*m)=1。
所以gcd(m,n-n/m*m)=1。
那么gcd(b,a%b)=1。
上代码。

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

数论基础:扩展欧几里得和乘法逆元,欧拉函数

扩展欧几里得算法(求ax+by=gcd(a,b)的一组特解)
欧几里得算法(求最大公约数)
gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}

扩展欧几里得
exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1;
y=0;
return;
}
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return;
}

斐蜀定理:一定存在ax+by=gcd(a,...

浅谈裴蜀定理&扩展欧几里得

裴蜀定理
\(a,b\) 是整数,且 \(\gcd(a,b)=d\),那么对于任意的整数 \(x,y\),\(ax+by\) 都一定是 \(d\) 的倍数。特别地,一定存在整数 \(x,y\),使 \(ax+by=d\) 成立。
换种说法,若 \(ax+by=c\) 有解,当且仅当 \(c\) 是 \(\gcd(a,b)\) 的倍数。
证明:
令 \(\gcd(a,b)=p\)。
一、必要性:如果有整数解,那么 \(c\) 是 \(p\) 的倍数。
\(a=a'*p,b=b'*p\)
\(ax+by=a'*p*x+b'*p*y=p*(a'x+b'y)=c\)。
因此 \(c\) 是 \(p\...

JS 求两个整数的最大公约数

求 a 和 b 两数的最大公约数的主要方式:
1. 欧几里得法

// 欧几里得法
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);

 
2. 更相减损法

// 更相减损法
const gcd = (a, b) => {
while (true) {
if (a > b) a -= b;
else if (a < b) b -= a;
else return a;
}
};

 

...

文章标题:欧几里得(扩展)算法
文章链接:https://www.dianjilingqu.com/50819.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>