扩展欧几里得算法详解(exgcd)
一、前言
本博客适合已经学会欧几里得算法的人食用~~~
二、扩展欧几里得算法
为了更好的理解扩展欧几里得算法,首先你要知道一个叫做贝祖定理的玄学定理: 即如果a、b是整数,那么一定存在整数x、y使得$ax+by=gcd(a,b)$。
通俗的说就是:如果$ax+by=c$有解,那么$c\%gcd(a,b)=0$
扩展欧几里得算法就是来求解$ax+by=c$这个方程的(判断有无解仅需使用欧几里得算法即可)。
我们不妨从递归到底的情况来入手。
当$b==0$时,显然有:
$\begin{cases}x=1\\y=0\end{cases}$
为一组合法解
问题是如何解决不是递归最底层的情况。
考虑往下递归时候的操作,不妨设本层的$a$为$a_1$,$b$为$b_1$下一层的$a$为$a_2$,$b$为$b_2$
结合gcd的递归过程,显然有$a_2=b_1,b_2=a_1\%b_1$
由于递归算法总是先get到下层的解,因此我们可以直接设$a_2x_2+b_2y_2=gcd(a_2,b_2)$的解为$x_2,y_2$
然后我们来思考如何根据下层解得到上层的解。
考虑取余运算的性质:显然有:$a\%b=a-(\lfloor a\div b\rfloor)*b$
然后我们把这个结论套进刚刚的式子中,用$a_1$和$b_1$替换$a_2$和$b_2$,这个过程大概是这个样子的:
$a_2x_2+b_2y_2=gcd(a_2,b_2)\\=>b_1x_2+(a_1\%b_1)y_2=gcd(a_2,b_2)\\=>b_1x_2+(a_1-a_1\div b_1*b_1)y_2=gcd(a_2,b_2)\\=>b_1x_2+a_1y_2-(a_1\div b_1)b_1y_2=gcd(a_2,b_2)\\=>a_1y_2+b_1(x_2-a_1\div b_1*y_2)=gcd(a_2,b_2)$
经过以上非常基础的推算,我们可以得到$a_1,b_1,x_1,y_1,x_2,y_2$如下的关系:
$\begin{cases}x_1=y_2\\y_1=x_2-a_1\div b_1*y_2\end{cases}$
于是递归计算即可。
exgcd的代码实现大概长这样:
void exgcd(int a,int b,int &x,int &y)
{
if(b==)
{
x=;y=;
return;
}
exgcd(b,a%b,x,y);
int x1=x,y1=y;
x=y1;y=x1-a/b*y1;
}
exgcd代码实现
三、例题分析
这道题开门见山,直接就说出了要求什么,可谓NOIP茫茫毒瘤题中一股清流
我们要求的是$ax≡1 (mod b)$,不妨设$ax+by=1$,接下来我们就可以搬出我们的exgcd的模板,轻松秒掉这道题。
值得注意的是,我们求出来的是最小解,而题目要求的是最小正整数解,因此如果不符合条件的话还要往上累加。
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int x,y,a,b;
void exgcd(int a,int b,int &x,int &y)
{
if(b==)
{
x=;y=;
return;
}
exgcd(b,a%b,x,y);
int x1=x,y1=y;
x=y1;y=x1-a/b*y1;
}
signed main()
{
cin>>a>>b;
exgcd(a,b,x,y);
while(x<)x=(x+b)%b;
cout<<x<<endl;
return ;
}
洛谷P1082同余方程
(贝祖定理内容部分来自这位大佬的博客)
最新文章
- 如何合并两个Docker 镜像
- HDU2048
- Pig + Ansj 统计中文文本词频
- TYVJ1939 玉蟾宫
- MongoDB 入门之查询(find)
- pdftk的使用介绍
- js遍历数组对象和非数组对象
- html常用的知识点以及混合框架
- SSL证书:Web加密使互联网更安全
- Linux内存机制以及手动释放swap和内存
- hdu 5592 BestCoder Round #65(树状数组)
- XML解析的四种方法 建议使用demo4j解析 测试可以用
- C语言作业06--结构体&;文件
- 关于Struts2自动装配和访问Servlet API
- How to write threats to validity?
- 使用vivado将bit文件转化为mcs文件
- 构建模式--Adapter模式(JAVA)
- keras环境
- mysql忘记密码解决方法
- learngin uboot design parameter recovery mechanism