笔记|扩展欧几里得算法+板子+例题板子|数论|算法&理论

目录
欧几里得算法
扩展欧几里得算法
例题
欧几里得算法：
有两个数a,b，求这两个数的最大公约数
欧几里得的一个定理：gcd(a,b)=gcd(b,a%b)
这样，就可以在近乎log的时间复杂度里求解a和b的最大公约数
这就是欧几里得算法
代码：

int gcd(int x,int y) { return y==0?x:gcd(y,x%y); }

扩展欧几里得算法
现在，已知 a 和 b 的最大公约数 gcd ，那么，我们一定能够找到这样的 x 和 y ，使得: a*x + b*y = gcd；
这是一个不定方程，必定有多组解，但是只要找到一组特殊的解 x0 和 y0，就可以用 x0 和 y0 表示出整个不定方程的通解：
x = x0 + (b/gcd)*t
y = y0 – (a/gcd)*t
因为欧几里德算法递归停止的状态是： a= gcd，b = 0
那么，只要 a = gcd 的系数是 1 ，那么只要 b 的系数是 0 或者其他值
然后从该最终状态反推到最初状态
假设当前我们要处理的是求出 a 和 b的最大公约数，并求出 x 和 y 使得 a*x + b*y= gcd ，而我们已经求出了下一个状态：b 和 a%b 的最大公约数，并且求出了一组x1 和y1 使得： b*x1 + (a%b)*y1 = gcd
因为 a%b = a - (a/b)*b 那么：
gcd = b*x1 + (a-(a/b)*b)*y1
= b*x1 + a*y1 – (a/b)*b*y1
= a*y1 + b*(x1 – a/b*y1)
对比之前状态：求一组 x 和 y 使得：a*x + b*y = gcd
这里：
x = y1
【笔记|扩展欧几里得算法+板子+例题】y = x1 – a/b*y1
以上就是扩展欧几里德算法的全部过程，依然用递归写：

int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int ans=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return ans; }

欧几里德算法部分好像只能用来求解最大公约数，
但是扩展欧几里德算法就不同了，既可以求出最大公约数，还可以顺带求解出使得： a*x + b*y = gcd 的通解 x 和 y
比如：求解形如 a*x +b*y = c 的通解
给出计算模板：

int cal(int a,int b,int c) { int x,y; int gcd=exgcd(a,b,x,y); if(c%gcd!=0)return -1; x*=c/gcd; if(b<0)b=-b; int ans=x%b; if(ans<=0)ans+=b; return ans; }

还有最小整数解之类的问题，但都是大同小异
例题
OJ 3609
求最小逆元【裸的求逆元模板题，c=1】

#include #include #include #include #include using namespace std; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int ans=exgcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; return ans; } int cal(int a,int b) { int x,y; int gcd=exgcd(a,b,x,y); if(1%gcd!=0)return -1; x*=1/gcd; if(b<0)b=-b; int ans=x%b; if(ans<=0)ans+=b; return ans; } int main() { int t; scanf("%d",&t); while(t--) { int a,b; scanf("%d%d",&a,&b); int ans=cal(a,b); if(ans==-1)puts("Not Exist"); else printf("%d\n",ans); } }

ZOJ 3593
求最小的步数；这里求到最后就是求|x|+|y|的最小值
线性规划，画出图之后可知最下面的交点处x=y时值最小
但是x不等于y，所以枚举其附近的点
然后联立x及y的通解（在x=y的情况下）求出T
再分类讨论xy 同向异向的问题

#include #include #include #include #include #include #include using namespace std; typedef long long LL; LL exgcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1; y=0; return a; } LL ans=exgcd(b,a%b,x,y); LL t=x; x=y; y=t-a/b*y; return ans; } LL cal(LL a,LL b,LL c) { LL x,y; LL gcd=exgcd(a,b,x,y); if(c%gcd!=0)return -1; x*=c/gcd; y*=c/gcd; a/=gcd; b/=gcd; LL ans=LLONG_MAX; LL f; LL mid=(y-x)/(a+b); for(LL T=mid-1; T<=mid+1; T++) { if(abs(x+b*T)+abs(y-a*T)==abs(x+b*T+y-a*T))///即x，y同号，同方向走 f=max(abs(x+b*T),abs(y-a*T)); ///可以走x步a，y步b，还可以走c//(a+b); 所以选择步数最多的那种走法 else f=fabs(x+(-(y-(a+b)*T))); ///朝不同的方向走，走了x+y步x+(-y)使同号 ans=min(ans,f); } return ans; } int main() { int t; scanf("%d",&t); while(t--) { LL A,B,a,b; scanf("%lld%lld%lld%lld",&A,&B,&a,&b); LL ans=cal(a,b,B-A); printf("%lld\n",ans); } }

POJ 1061青蛙的约会【裸的扩展欧几里得】
不过这里有一个小处理，就是一个静止另一个做相对运动
所以传参是m-n，L，y-x

#include #include #include #include #include #include #include using namespace std; typedef long long LL; LL exgcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1; y=0; return a; } LL ans=exgcd(b,a%b,x,y); LL t=x; x=y; y=t-a/b*y; return ans; } LL cal(LL a,LL b,LL c) { LL x,y; LL gcd=exgcd(a,b,x,y); if(c%gcd!=0)return -1; x*=c/gcd; if(b<0)b=-b; LL ans=x%b; if(ans<=0)ans+=b; return ans; } int main() { LL x,y,m,n,L; scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L); LL ans=cal(m-n,L,y-x); if(ans==-1)puts("Impossible"); else printf("%lld\n",ans); }

HDU 2669
裸题，但是这里输出的是两个数，注意输出就好

#include #include #include #include #include #include #include using namespace std; typedef long long LL; LL exgcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1; y=0; return a; } LL ans=exgcd(b,a%b,x,y); LL t=x; x=y; y=t-a/b*y; return ans; } LL cal(LL a,LL b,LL c) { LL x,y; LL gcd=exgcd(a,b,x,y); if(c%gcd!=0)return -1; x*=c/gcd; b/=gcd; if(b<0)b=-b; LL ans=x%b; if(ans<=0)ans+=b; return ans; } int main() { LL a,b; while(~scanf("%lld%lld",&a,&b)) { LL ans=cal(a,b,1); if(ans==-1)puts("sorry"); else printf("%lld %lld\n",ans,(1-ans*a)/b); } }