欧几里得算法

秒速五厘米 2022-10-01 13:46 235阅读 0赞

欧几里得算法中，计算 x, y 的最大公约数的方法是辗转相除，例如：

gcd (26, 15)

26 % 15 = 1 ... 11  
15 % 11 = 1 ... 4  
11 % 4 = 2 ... 3  
4 % 3 = 1 ... 1  
3 % 1 = 3 ... 0

可知，gcd (26, 15) = 1

如果 gcd(x, y) = r，那么有 ax + by = r，可以看出，上面的步骤实际上是可以直接得出 a, b 的：

26 % 15 = 1 ... 11 => 11 = 26 - 15 1 1 -1  
15 % 11 = 1 ... 4 => 4 = 15 - 11 = 15 - (26 - 15) = -26 + 2\*15 1 -1 2  
11 % 4 = 2 .. 3 => 3 = 11 - 4\*2 = (26 - 15) - (-26 + 15) \* 2 = 3\*26 - 5\*15 2 3 -5  
4 % 3 = 1 ... 1 => 1 = 4 - 3 = (-26 + 2\*15) - (3\*26 - 5\*15) = -4\*26 + 7\*15 1 -4 7  
3 % 1 = 3 ... 0

在每一轮，我们都可以得到一个模的表达式为：ri = aix + biy  
如果不考虑第一轮和第二轮，那么ai 和 bi 可以表示为(qi 为每一轮得到的商)：

ai = ai-2 - qi \* ai-1  
bi = bi-2 - qi \* bi-1

现在来考虑第一轮和第二轮，按照上面的公式，可以认为

a-1 = 1, b-1 = 0  
a0 = 0, b0 = 1

有了这两对预设值，上面的两个公式就成立了

求逆元，由上面可以看出，gcd(x, y) = 1 的时候  
如果 ax + by = 1，那么 ax = -by + 1 => ax = 1 (mod b)  
这时候，a 即是 x 的逆元  
int gcd (int x, int y, int \*a1, int \*a2, int \*b1, int \*b2)  
\{  
int q, r, a, b;  
q = x / y;  
r = x % y;  
a = \*a2 - q\*(\*a1);  
b = \*b2 - q\*(\*b1);  
if (0 == r) \{  
return y;  
\}  
\*a2 = \*a1;  
\*b2 = \*b1;

\*a1 = a;  
\*b1 = b;  
return gcd (y, r, a1, a2, b1, b2);  
\}

转载于:https://blog.51cto.com/jeick/144556

发表评论取消回复

表情：

评论列表（有 0 条评论，235人围观）

还没有评论，来说两句吧...

相关阅读

相关欧几里得算法

一.自然语言描述：计算两个非负整数p和q的最大公约数：若q是0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。二.Jav

╰+哭是因爲堅強的太久メ/ 2024年03月23日 17:45/ 0 赞/ 81 阅读

相关扩展欧几里得算法 AcWing 877. 扩展欧几里得算法

扩展欧几里得算法 AcWing 877. 扩展欧几里得算法原题链接 [AcWing 877. 扩展欧几里得算法][AcWing 877.] 算法标签数学

不念不忘少年蓝@/ 2023年09月28日 11:41/ 0 赞/ 24 阅读

相关欧几里得算法

欧几里得算法中，计算 x, y 的最大公约数的方法是辗转相除，例如： gcd (26, 15) 26 % 15 = 1 ... 11 15 % 11 = 1 ... 4

秒速五厘米/ 2022年10月01日 13:46/ 0 赞/ 236 阅读

相关欧几里得和扩展欧几里得算法

（一）欧几里得算法又称辗转相除法，是求解两个数的最大公约数的算法，基本定义为：设 a=qb+r，其中a，b，q，r都是整数，则：gcd（a，b）= gcd（b，r）利用

ゞ浴缸里的玫瑰/ 2022年08月21日 03:20/ 0 赞/ 268 阅读

相关扩展欧几里得算法

问题描述：求解二元一次方程ax+by=c。问题分析：上述的二元一次方程可以用同余方程来进行描述：ax≡cmod(b) 两个问题可以进行转换，但是都可以用扩展的欧几

心已赠人/ 2022年06月15日 10:00/ 0 赞/ 263 阅读

相关算法——欧几里得算法

计算二个非负整数p和q的最大公约数。若q=0，则最大的公约数为p，否则，将p/q得到的余数r，p和q的最大公约数即为q和r的最大公约数 pubulic static int

素颜马尾好姑娘i/ 2022年04月03日 04:48/ 0 赞/ 245 阅读

相关数论杂谈——欧几里得算法及扩展欧几里得

数学是oi的重要基础，所以说数论在oi中占据了非常重要的地位，因此，学好数学，对于一个oier来说也是非常重要的。 oi中的数学，其实也就和数竞并没有什么区别。欧几里得法

落日映苍穹つ/ 2021年12月23日 23:55/ 0 赞/ 381 阅读

相关欧几里得算法和扩展欧几里得算法数论基础

　　这两个算法可以说是OI里数学模块最重要的基础了（如果位运算不算数学的话）。一.欧几里得算法（Euclidean Algorithm）　　模板水题：[LOJ P121

r囧r小猫/ 2021年12月12日 07:19/ 0 赞/ 341 阅读

相关扩展欧几里得算法

下面直接使用简称exgcd就好。先引入紫书上的一个经典问题，求直线方程ax+by+c=0的所有整数解。我们先来看一个简单的，求ax+by=gcd(a,b)的一组整数解。

今天药忘吃喽~/ 2021年09月29日 21:02/ 0 赞/ 425 阅读

相关欧几里得算法

一代码 package Euclid; / Copyright (C), 2020-2020, XXX有限公司 Fi

红太狼/ 2021年07月24日 16:01/ 0 赞/ 433 阅读