扩展欧几里得模板

1.求ax+by=gcd(a,b)的任意一组解：

因为gcd(a,b)=gcd(b,a%b)

为计算方便 , 递归的时候交换x,y位置，那么原式就变为

by+(a%b)x=gcd(a,b)

=>by + ( a - a / b (下取整) * b) * x = gcd(a,b)

=>ax + b(y - a / b * x) = gcd(a,b)

#include<iostream> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1;y=0; return a; } int r=exgcd(b,a%b,y,x); y-=a/b*x; } int main() { int n; cin>>n; while(n--) { int x,y,a,b; scanf("%d%d",&a,&b); int r=exgcd(a,b,x,y); printf("%d %d\n",x,y); } return 0; }

2.求ax+by=c的解

若c%gcd(a,b)！=0那么无解

根据上面求出一组x0, y0满足a * x0 + b * y0 = gcd(a,b)

令d=c/gcd(a,b), t=c/d

ax0+by0=d

ab/d+ax0-ab/d+by0=d

a(x0+b/d)-b(y0-a/d)=d

两边同时乘以t， 即解得 x=(x0+b/d)*t, y=(y0-a/d)*t

#include<iostream> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1;y=0; return a; } int r=exgcd(b,a%b,y,x); y-=a/b*x; } int main() { int a,b,c,x0,y0,x,y; scanf("%d%d%d",&a,&b,&c); int d=exgcd(a,b,x0,y0); if(c%d!=0) printf("no solution\n"); else { int t=c/d; x=(x0+b/d)*t; y=(y0-a/d)*t; printf("x=%d y=%d\n",x,y); } return 0; }