扩展欧几里得算法
- 扩展欧几里得算法证明+应用
- ==欧几里得算法==
- ==扩展欧几里得算法==
- 应用1：求一元二次线性方程的整数解
- 应用二：求ax=c(mod p)
- 应用三：求乘法逆元ax=1(mod p)
- 题目练习
- 如果你觉得有所收获，能否向你讨一个赞，以此激发博主的开发热情，谢谢！
扩展欧几里得算法证明+应用
扩展欧几里得算法顾名思义是由欧几里得算法延伸出来的一个知识点，在搞懂扩展欧几里得算法之前不妨先来熟悉一下什么是欧几里得算法(又名辗转相除法)
欧几里得算法
1.应用：主要用于求解两个数a和b的最大公约数,我们不妨设(a>b),其公式为gcd(a,b)=gcd(b,a%b)=gcd(a%b,b%(a%b))=…=gcd(x,0),这里的x即为最大公约数.
2.下面展示代码：
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
int gcd(int a,int b)
{
while(b!=0)
{
int r=a%b;
a=b;
b=r;
}
return a;
}
扩展欧几里得算法
由贝祖定理得：任意两个整数a,b,最大公约数为d=gcd(a,b),那么对于任意的整数x,y，ax+by=m,构成的m一定是d的整数倍(即m%d=0)
应用1：求一元二次线性方程的整数解
根据贝祖定理我们可以求得ax+by=c直线上的所有整数解(当然解的个数是无限的)，往往题中会让你求其中的一个特殊性质的解(例如：求x为最小的非负整数对应的解(x,y))
思路：我们不妨先求出ax+by=gcd(a,b)的解，然后把解乘以c/gcd(a,b)就得到了原方程ax+by=c的解，细心的同学已经发现c/gcd(a,b)可能不是整数，这时候说明原方程没有整数解(即x和y不全为整数)（不满足贝祖定理）
步骤一：求ax+by=gcd(a,b)的特解
我们知道对于任意整数a,b都有ax+by=gcd(a,b)成立，所以得到
1.ax0+by0=gcd(a,b)
2.递归迭代一次得到 bx1+(a%b)y1=gcd(b,a%b)
3.gcd(a,b)=gcd(b,a%b)
由1，2，3式子得ax0+by0=bx1+(a%b)y1
(a%b)y1=(a-a/b*b)*y1
故ax0+by0=bx1+(a-a/b*b)y1
解得x0=y1,y0=x1-(a/b)*y1
不难发现，要得到x0,y0就要先求出下一次迭代的解x1,y1，要得到x1,y1就要再迭代一次求出x2,y2…一直迭代到最后
所以递归迭代到最后ax+by=gcd(a,0)=a, a×1+ b×0=a,所以此时子解为x=1，y=0.然后不断回溯上去就得到了正解x0，y0
代码如下：
int exgcd(int a,int b,int &d,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
d=a;
}
else
{
exgcd(b,a%b,d,x,y);
int t=y;
y=x-(a/b)*y;
x=t;
}
return 0;
}
步骤二：根据特解求通解
已知特解x0,y0
1.ax0+by0=gcd(a,b)
2.ax’+by’=gcd(a,b)
不难得出
x’=x0+b/gcd(a,b)*k (k为任意整数)
y’=y0-a/(gcd(a,b)*k
有人会问为什么不可以直接x’=x0+bk,y’=y0-ak？
因为答案会有遗漏，b和b/gcd(a,b)都是整数，然而b/gcd(a,b)<=b,说到这应该知道为什么答案会遗漏了吧
最小的非负整数解x’是多少呢？
其实就是( x0%( b/gcd(a,b) ) )+b/gcd(a,b) )% ( b/gcd(a,b))
有人会问为什么不直接写成x0%( b/gcd(a,b) )，因为x0可能是负数
步骤3：求出原方程的解
上面已经求出了ax0+by0=gcd(a,b)的特解(x0,y0)，所以我们只需要把他等比例放大c/gcd(a,b)倍即可，所有解亦是如此
原方程的通解为
切记不能直接把x’,y’同比例放大不然会漏解,错误答案如下所示
X=x0c/gcd(a,b)+k(b*c)/(gcd(a,b)*gcd(a,b))
Y=y0c/gcd(a,b)-k(a*c)/(gcd(a,b)*gcd(a,b))
正确解如下
X=x0c/gcd(a,b)+kb/(gcd(a,b)
Y=y0c/gcd(a,b)-ka/gcd(a,b)
应用二：求ax=c(mod p)
与前面类似，ax=c(mod p)等同于ax%p=c%p,所以直接转化为一元二次方程问题求ax+py=c的解
应用三：求乘法逆元ax=1(mod p)
解法类似，也是转化为一元二次方程ax+py=1的解
我们一般把x的最小非负整数解作为a的乘法逆元
题目练习
青蛙约会
题目描述
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
输入格式
输入只包括一行5个整数x，y，m，n，L
其中0<x≠y < =2000000000，0 < m、n < =2000000000，0 < L < =2100000000。
输出格式
输出碰面所需要的天数，如果永远不可能碰面则输出一行"Impossible"。
输入
1 2 3 4 5
输出
4
题解
由题意我们可以列出方程
x+my=y+nt（%L)
设未知数t,q分别表示青蛙A和青蛙B跳的次数
那么可以得到
(m-n)t+Lq=y-x(modL)
设m-n=A，y-x=B，代入得到At+Lq=B(modL)
因为我们已知ax+by=gcd(a,b)这样的一个公式
所以我们先求At+Lq=gcd(A,L)，用扩展欧几里得可以得到一个特解x0；
因为gcd(A,L)要求A,L都要大于0，如果A<0,等式两边同乘以一个负号即可，也即A=-A,B=-B，如果B<0,B+=L;
最后我们把x0*B/gcd(A,L),就得到了原方程的解
但是题目要求最小的正整数x0，我们设s=L/gcd(A,L),x0=(x0%s+s)%s就是答案
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll &x,ll &y,ll &g,ll a,ll b)
{
if(b==0)
{
x=1;
y=0;
g=a;
return 0;
}
exgcd(x,y,g,b,a%b);
ll x1=y;
ll y1=x-(a/b)*y;
x=x1;
y=y1;
return 0;
}
int main()
{
ll m,n,L;
ll t,q,g;
ll x,y;
cin>>x>>y>>m>>n>>L;
ll a=m-n;
ll c=y-x;
ll b=L;
if(a<0)
{
a=-a;
c=-c;
if(c<0) c+=L;
}
exgcd(t,q,g,a,b);
if(c%g!=0||m==n)
{
printf("Impossible\n");
return 0;
}
ll s=L/g;
t=t*c/g;
ll ans=(t%s+s)%s;
cout<<ans;
return 0;
}
接下来我们趁热打铁，试着谢谢这道题
五指山
西游记中孙吾空大闹天宫，如来佛祖前来降伏他，说道：“我与你打个赌赛；你若有本事，一筋斗打出我这右手掌中，算你赢，再不用动刀兵苦争战，就请玉帝到西方居住，把天宫让你；若不能打出手掌，你还下界为妖，再修几劫，却来争吵。”
那大圣闻言，暗笑道：“这如来十分好呆！我老孙一筋斗去十万八千里。他那手掌，方圆不满一尺，如何跳不出去？”急发声道：“既如此说，你可做得主张？”佛祖道：“做得！做得！”伸开右手，却似个荷叶大小。那大圣收了如意棒，抖擞神威，将身一纵，站在佛祖手心里，却道声：“我出去也！”你看他一路云光，无影无形去了。大圣行时，忽见有五根肉红柱子，撑着一股青气。他道：“此间乃尽头路了。这番回去，如来作证，灵霄殿定是我坐也。”翻转筋斗云，径回本处，站在如来掌：“我已去，今来了。你教玉帝让天宫与我。”
如来骂道：“你正好不曾离了我掌哩！”大圣道：“你是不知。我去到天尽头，见五根肉红柱，撑着一股青气，我留个记在那里，你敢和我同去看么？”如来道：“不消去，你只自低头看看。”那大圣睁圆火眼金睛，低头看时，原来佛祖右手中指写着“齐天大圣，到此一游。”大圣大吃了一惊道：“有这等事！有这等事！我将此字写在撑天柱子上，如何却在他手指上？莫非有个未卜先知的法术？我决不信！不信！等我再去来！”
好大圣，急纵身又要跳出，被佛祖翻掌一扑，把这猴王推出西天门外，将五指化作金、木、水、火、土五座联山，唤名“五行山”，轻轻的把他压住。
我们假设佛祖的手掌是一个圆圈（所以任凭大圣一个筋斗云十万八千里也是飞不出其手掌心），圆圈的长为n，逆时针记为：0，1，2，…,n-1，而大圣每次飞的距离为d.现在大圣所在的位置记为x,而大圣想去的地方在y。现在要你告诉大圣至少要多少筋斗云才能到达目的地。
Input
有多组测试数据。
第一行是一个正整数T，表示测试数据的组数。
每组测试数据包括一行，四个非负整数，n（2 < n < 10^9），表示如来手掌圆圈的长度；d(0 < d < n),筋斗所能飞的距离；x(0 <= x < n),大圣的初始位置；y(0 <= y < n)，大圣想去的地方。
注意孙悟空的筋斗云只沿着逆时针方向翻。
Output
对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。如果无论翻多少个筋斗云也不能到达，输出“Impossible”.
Sample Input
2
3 2 0 2
3 2 0 1
Sample Output
1
2
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll &g,ll &x,ll &y)
{
if(b==0)
{
g=a;
x=1;
y=0;
return ;
}
else
{
ll x1,y1;
exgcd(b,a%b,g,x,y);
x1=y;
y1=x-(a/b)*y;
x=x1;
y=y1;
}
return ;
}
int main()
{
int t ;
cin>>t;
while(t--)
{
ll n,d,x,y,g;
ll t,p;
cin>>n>>d>>x>>y;
ll c=y-x;
if(d<0)
{
d=-d;
c=-c;
if(c<0) c+=n;
}
exgcd(d,n,g,t,p);
if(c%g!=0)
{
printf("Impossible\n");
}
else
{
t=t*c/g;
ll s=n/g;
t=(t%s+s)%s;
printf("%lld\n",t);
}
}
return 0;
}
如果你觉得有所收获，能否向你讨一个赞，以此激发博主的开发热情，谢谢！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
