exgcd学习笔记

前言

今天膜你赛竟然要套$exgcd$

gcd

exgcd

形如$ax+by=c$的方程,当$gcd(a,b)|c$时,存在整数解$x,y$。
也就是说$exgcd$可以解$ax+by=gcd(a,b)$的方程。
令$a=b,b=a\mod b$,那么$bx+a\mod b\times y=gcd(b,a\mod b)$。
因为$gcd(a,b)=gcd(b,a\mod b)$。
所以$bx+a\mod b\times y=gcd(a,b)$。
又因为$a\mod b=a-b\times \lfloor {a/b} \rfloor$
所以$bx+(a-b\times \lfloor {a/b} \rfloor)\times y =gcd(a,b)$。
整理得:$a\times y+b\times (x-\lfloor {a/b} \rfloor)=gcd(a,b)$。
所以可以转化为$x_{new}=y,y_{new}=x-\lfloor {a/b} \rfloor$,继续求解即可。
当$b=0$时,$y=0,x=1,gcd=a$。

暂无评论

发送评论 编辑评论


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