GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
GoldenPotato的ACM小屋
一名HITer/LLer/ACMer的ACM(前OI)博客
  1. 首页
  2. 数学
  3. 正文

扩展欧几里得算法+推论

2019年02月25日 302点热度 0人点赞 0条评论

什么是扩展欧几里得?

扩展欧几里得算法是建立在欧几里得算法(gcd)之上。

首先,我们知道有$ax+by=gcd(a,b)$

我们怎么求这个$x,y$呢?

这时候我们就得使用exgcd算法,我们来推导一下吧!

$a*x+b*y=gcd(a,b)$

$a*x+b*y=gcd(b,a\% b)$

$a*x+b*y=b*x'+(a- \left \lfloor \frac{a}{b} \right \rfloor*b)*y'$

$a*x+b*y= a*y'+b*(x'-\left \lfloor \frac{a}{b} \right \rfloor*y')$

因此,根据系数对应,我们得到了

$x=y'$,$y=x'-\left \lfloor \frac{a}{b} \right \rfloor*y'$

那这个式子我们显然可以在递归里面顺带算出来嘛。

再想一想,我们gcd的递归出口为$b=0$,即$a*x=gcd(a,b)$,所以说我们的$x,y$的递归出口也为$x=1,y=0$

代码大概长这样qwq:

long long exgcd(long long A,long long B,long long &x,long long &y)
{
    if(B==0) 
    {
        x=1,y=0;
        return A;
    }
    long long t=exgcd(B,A%B,x,y),tx=x;
    x=y;
    y=tx-(A/B)*y;
    return t;
}

酱紫,我们就求出了$x,y$的一组解$x_0,y_0$


进一步推导

如果我们要求x的最小正整数解,那不免要求x的通项公式。

首先我们的推导建立在已经求出了一组$(x_0,y_0)$使得$a\times x+b\times y=gcd(a,b)$

我们要求的$x$的通项公式是建立在$x_0$之上的,我们假设$x=x_0+p$,$y=y_0-q$

现在问题就变为了如何求这个$p$。

原式变为:
$$a(x_0+p)+b(y_0-q)=gcd(a,b)$$

展开得:
$$ax_0+ap+by_0-qb=gcd(a,b)$$

与原式$ax_0+by_0=gcd(a,b)$相减得
$$ap=bq$$

$$p=\frac{b*q}{a}$$

我们设$d=gcd(a,b)$,有$a=a'd$,$b=b'd$

将上一个式子上下同时除以$d$得
$$p=\frac{b'*q}{a'}$$

因为$p$为正整数,因此我们的$q$至少等于$a'$才能使得$p$的取值最小
$$p=b*\frac{a'}{a}=b*\frac{1}{d}=b*\frac{1}{gcd(a,b)}$$

解毕,我们得到了$x$的通项公式$x=x_0+k*\frac{b}{gcd(a,b)}$

.

完结撒花(*´゚∀゚`)ノ

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数学
最后更新:2019年02月28日

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

点赞
< 上一篇
下一篇 >

文章评论

取消回复

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 34
  • 23
  • 79,010
  • 22,848

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号