拓展欧几里得算法与应用

欧几里得算法

即:$gcd(a,b)=gcd(b,a$%$b)$
欧几里得算法在oi里非常常用,几乎每个数学题都有欧几里得算法——$gcd$。
说白了就是求最大公约数。一行代码搞定:

拓展欧几里得算法

定理

定理1:设$a$和$n$不全为$0$,则存在整数$x,y$,满足$ax+by=gcd(a,b)$。
证明:
当$b=0$时,$gcd(a,b)=a$。因为$1\times a + 0 \times 0 =a$,所以,$ax+by=gcd(a,b)$有一组解为$x=1,y=0$。
当$b \not = 0 $时,$gcd(a,b)=gcd(b,a$%$b)$。
设$x’,y’$满足$gcd(a,b)=bx’+(a$%$b)y’=gcd(b,a$%$b)$。
那么,$bx’+(a$%$b)y’=gcd(a,b)$
即,$bx’+(a-(a/b)\times b )y’=gcd(a,b)$,其中$’/’$为整除。
所以,$bx’+ay’-(a/b)\times b \times y’=gcd(a,b)$
即,$ay’+b\times (x’-(a/b)\times y’)=gcd(a,b)$
那么可以继续递归拓展欧几里得:$x=y’,y=(x’-(a/b)\times y’)$。
因为欧几里得算法的递归过程,可知定理1成立。
证毕。

Code

拓展欧几里得算法的应用

问题

求解不定方程$ax+by=c$的所有整数解。

分析

当$gcd(a,b)$整除$c$时该方程有解。
设$g=gcd(a,b),a’=a/g,b’=b/g$。
我们可以用上文的拓展欧几里得算法来求出不定方程$a’x’+b’y’=1$的整数解$x’,y’$。
那么
$$a’c’x’+b’c’y’=c’$$
$$a’gc’x’+b’gc’y’=c’g$$
即:
$$ac’x’+bc’y’=c$$
所以$x_0=c’x’,y_0=c’y’$是方程的一组解。
因为不定方程$a’x+b’y=c’→$同余方程$a’x \equiv c'(mod \quad b’)$。所以$x$为$mod$ $b’$的一个剩余类,所以该补丁方程的通解为:
$$x=x_0+b’ \times t,y=y_0 -a’ \times t,(t \in Z)$$
当$gcd(a,b)$不能整除$c$时,就没有上文求解过程,方程无解。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇