扩展欧几里得【数论数论

m和n不全为零
一定存在gcd(m,n)==xm+ny
模板1

int exgcd(int m,int n,int &x,int &y)//返回gcd(m,n) { int x1,y1,x0,y0; x0=1; y0=0; x1=0; y1=1; x=0; y=1; int r=(m%n+n)%n; int q=(m-r)/n; x=0,y=1; while(r) { x=x0-q*x1; y=y0-q*y1; x0=x1; y0=y1; x1=x; y1=y; m=n; n=r; r=m%n; q=(m-r)/n; } return n; } int main() { int x,y; int m=6 ; int n= 2; int a =exgcd(6,2,x,y); printf("6*%d + 2*%d = %d \n",x,y,a ); return 0; }

6*0 + 2*1 = 2
[Finished in 0.0s]

模板2
x y为全局变量，不需要初始化

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

ax+by==gcd(a,b)

对于解一般不定式 ax+by==c是上式的整数倍
即仅当c%gcd(a,b)为0时有整数解 x,y
x=x0*c/gcd(a,b);
y=y0*c/gcd(a,b);

题目经常求最小的正x值有一个神奇的公式
x=x+b/gcd(a,b)*k
y=y-a/gcd(a,b)*k(k为任意整数)
即对每组x,y值都有ax+by==c成立
所以求得x后,
令s=b/gcd(a,b);
x=x(x%s+s)%s;
【扩展欧几里得【数论】x为最小正值