专栏文章

拓展欧几里得算法

___mt19937__
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq7lvdh
此快照首次捕获于
2025/12/04 00:16
3 个月前
此快照最后确认于
2025/12/04 00:16
3 个月前
查看原文

拓展欧几里得算法

欧几里得算法

一般形式

gcd(a,b)=gcd(a mod b,b)gcd(a,b)=gcd(a \bmod b,b)

证明

因为 gcd(a,b)=gcd(b,a−b)gcd(a,b)=gcd(b,a-b)，所以可以简化减法运算为模运算。
即 gcd(a,b)=gcd(b,a mod b)gcd(a,b)=gcd(b,a \bmod b)。

code

CPP
inline int gcd (register const int x, register const int y)
{
  
  return y == 0 ? x : gcd (y, x % y);
}

主要步骤

拓展欧几里得算法主要用来求一个形如 ax+by=kax + by = k 的不定方程的最小解。
((由翡蜀定理：ax+by=kax + by = k 的最小解为 gcd(a,b)gcd (a, b) ))。
具体过程如下：
当 b=0b = 0 时， 明显 k=ak = a， 那么就有 x=1,y=0x = 1, y = 0
然后我们就假设当前上一层的答案为x1,y1x_1,y_1，则可得：
gcd(a,b)=ax+bygcd(a,b) = ax + by
gcd(b,a mod b)=bx1+(a mod b)y1gcd(b,a \bmod b) = bx_1 + (a\bmod b)y_1
ax+by=bx1+(a mod b)y1ax + by = bx_1 + (a \bmod b)y_1
又因为 a mod b=a−⌊ab⌋ba \bmod b = a-\lfloor{a \over b}\rfloor b
所以 ax+by=bx1+ay1−b⌊ab⌋y1ax + by = bx_1 + ay_1 - b\lfloor {a \over b} \rfloor y_1
那么 x=y1x = y_1，y=x1−⌊ab⌋y1y = x_1 - \lfloor {a \over b} \rfloor y_1

code

CPP
inline int Ex_Gcd (register const int a, register const int b, register int &x, register int &y)
{
	
	if (not b)
	{
		
		x = 1;
		y = 0;
		
		return a;
	}
	
	register const int d(Ex_Gcd (b, a % b, x, y));
	register const int temp (y);
	
	y = x - (a / b) * y;
	x = temp;
	
	return d;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...