文章目录

欧几里得算法历史发展表示证明代码例题 扩展欧几里得算法表示求解方法代码其他定理:例题

欧几里得算法

历史发展

欧几里得算法用来求得两个数的最大公约数，大约公元前300年首次出现于几何原本，又称作辗转相除法，不过似乎不是来源于欧几里得，有人称来自于毕达哥拉斯学院的数学家。

虽然世界分隔，可是历史的进程似乎总会有相似，欧几里得算法后来先后被印度人、中国人独立发现。虽然语言不同、风俗不同、文化不同。但人们都发现了同样的真理，实是让人惊叹。

“欧几里得算法是所有算法的鼻祖，因为它是现存最古老的非凡算法。” ----高德纳，《计算机程序设计艺术，第二卷：半数值算法》，第二版 (1981), p. 318.

表示

g c d ( a , b ) gcd(a,b) gcd(a,b): 表示整数 a , b a,b a,b的最大公约数。 a ∣ d a | d a∣d: 表示 d d d能整除 a a a。

则欧几里得算法可以表示为:

g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b) = gcd(b, a\%b) gcd(a,b)=gcd(b,a%b)

证明

思路：令 D 1 D_1 D1​为 a , b a, b a,b的公约数集合， D 2 D_2 D2​为 b , a % b b, a\%b b,a%b的公约数集合。我们证明 D 1 = D 2 D_1 = D_2 D1​=D2​， 公约数集合相同，最大公约数自然相同。步骤: 证明 ∀ d ∈ D 1 , 则 d ∈ D 2 \forall d \in D_1, 则d\in D_2 ∀d∈D1​,则d∈D2​:

令 r = a % b ， 有 a = k b + r → r = a − k b 令r = a \% b， 有a = kb + r \rightarrow r = a - kb 令r=a%b，有a=kb+r→r=a−kb

∀ d ∈ D 1 , 有 a ∣ d , b ∣ d . 又 r = a − k b , 故 r ∣ d \forall d \in D_1, 有 a|d, b|d. 又 r = a -kb, 故 r|d ∀d∈D1​,有a∣d,b∣d.又r=a−kb,故r∣d

因 此 有 r ∣ d , b ∣ d , 故 d ∈ D 2 因此有 r|d, b|d, 故d \in D_2 因此有r∣d,b∣d,故d∈D2​.证明 ∀ d ∈ D 2 , 则 d ∈ D 1 \forall d \in D_2, 则d\in D_1 ∀d∈D2​,则d∈D1​:

∀ d ∈ D 2 , 有 r ∣ d , b ∣ d , 又 a = k b + r , 故 a ∣ d , 又 b ∣ d , 因 此 d ∈ D 1 \forall d \in D_2, 有 r|d, b|d, 又a = kb+r, 故a|d, 又b|d,因此d \in D_1 ∀d∈D2​,有r∣d,b∣d,又a=kb+r,故a∣d,又b∣d,因此d∈D1​.得证

代码

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

例题

线段上的格点数

扩展欧几里得算法

表示

扩展欧几里得算法是用递归的方式求解 x , y x, y x,y,使其满足。

a x + b y = g c d ( a , b ) ax + by = gcd(a, b) ax+by=gcd(a,b)

求解方法

采用递归思想

递归出口: b=0。

b = 0 , 则 g c d ( a , b ) = a , 因 此 x o u t = 1 , y o u t = 0 b = 0, 则gcd(a, b) = a, 因此x_{out}=1, y_{out}=0 b=0,则gcd(a,b)=a,因此xout​=1,yout​=0建立联系:

如何将b变成0呢？注意到欧几里得算法其实就是一个逐渐将b变成0的过程。借助欧几里得算法，我们有:

令 a x 1 + b x 2 = g c d ( a , b ) 令 ax_1 + bx_2 = gcd(a, b) 令ax1​+bx2​=gcd(a,b)

令 b x 2 + ( a % b ) y 2 = g c d ( b , a % b ) 令 bx_2 + (a\%b)y_2 = gcd(b, a\%b) 令bx2​+(a%b)y2​=gcd(b,a%b)

由 欧 几 里 得 定 理 ， g c d ( a , b ) = g c d ( b , a % b ) , 因 此 由欧几里得定理， gcd(a, b) = gcd(b, a\%b), 因此 由欧几里得定理，gcd(a,b)=gcd(b,a%b),因此

a x 1 + b x 2 = b x 2 + ( a % b ) y 2 = b x 2 + ( a − a / b ∗ b ) y 2 （ 针 对 C 语 言 ） ax_1 + bx_2 = bx_2 + (a\%b)y_2 = bx_2 + (a-a/b*b)y_2（针对C语言） ax1​+bx2​=bx2​+(a%b)y2​=bx2​+(a−a/b∗b)y2​（针对C语言）

我 们 已 知 底 层 出 口 的 ( x o u t , y o u t ) ， 因 此 我 们 需 要 求 出 ( x , y ) 的 递 归 式 我们已知底层出口的(x_{out},y_{out})，因此我们需要求出(x,y)的递归式 我们已知底层出口的(xout​,yout​)，因此我们需要求出(x,y)的递归式

对 a , b 合 并 同 类 项 ， a x 1 + b y 1 = a y 2 + b ∗ ( x 2 − a / b ∗ y 2 ) 对a,b合并同类项，ax_1+by_1 = ay_2 + b * (x_2 - a/b*y_2) 对a,b合并同类项，ax1​+by1​=ay2​+b∗(x2​−a/b∗y2​)

因 此 x 1 = y 2 , y 1 = x 2 − a / b ∗ y 2 因此x_1 = y_2, y_1 = x_2 - a/b*y_2 因此x1​=y2​,y1​=x2​−a/b∗y2​

这样自底向上，便可求得最终的 ( x , y ) (x,y) (x,y)

代码

int extend_ojld(int a, int b, int &x, int &y){int d;if(b == 0){d = a;x = 1;y = 0;}else{d = extend_ojld(b, a%b, y, x);y -= (a / b) * x;}return d;}

其他定理:

若 n ∣ g c d ( a , b ) , 则 a x + b y = n 必 定 有 整 数 解 ( x , y ) ， 否 则 无 解 n | gcd(a,b) , 则ax+by = n必定有整数解(x, y)， 否则无解 n∣gcd(a,b),则ax+by=n必定有整数解(x,y)，否则无解有时候我们需要求得最小的正整数x m i n x_{min} xmin​满足 a x m i n ≡ n ( m o d b ) ax_{min} \equiv n(mod \ b) axmin​≡n(modb)， 我们将其化为 a x + b y = n ax + by = n ax+by=n， 使用扩展欧几里得算法求得一个解 x , y x, y x,y. 然后我们求得基础解 x b a s e = x ∗ n / g c d ( a , b ) x_{base} = x * n/gcd(a,b) xbase​=x∗n/gcd(a,b), 然后求得最小区间 s = b / g c d ( a , b ) s = b/gcd(a,b) s=b/gcd(a,b), 最后 x m i n = ( x b a s e % s + s ) % s x_{min} = (x_{base}\%s + s) \% s xmin​=(xbase​%s+s)%s 证明：略。

例题

青蛙的约会C Looooops