扩展欧几里得求通解、最小正整数解

扩欧求出来的解x,y是方程:ax+by=gcd(a,b)的解

x0=x*c/gcd

y0=y*c/gcd

x0,y0是方程ax+by=c的解

那么怎么求方程ax+by=c的通解呢?

让x0向左、右平移n格,y的变化(n为整数)

y0=(c-a*x0)/b

y1=(c-ax1)/b=(c-a(x0+n))/b=y0-a/b*n

也就是说x1=x0+n;y1=y0-a/b*n

把a/b转换为整数:

x1=x0+b*n

y1=y0-a*n

这样是不是就得到通解了?再想想,x每次变化b个单位真的能得到通解吗?

b/=gcd(a,b)

a/=gcd(a,b)

这样就好啦,因为把a,b化到最小,使得n前的系数最小,可得更多的解

int x,y,kx,ky;
int gcd=extgcd(a,b,x,y);
x*=c/gcd;
y*=c/gcd;
kx=b/gcd;
ky=-a/gcd;
//通解就是:x+kx*n,y+ky*n

得到通解后,怎么求最小正整数解呢?

已知:x+b/gcd*n是x的通解(相当于x每次可以增减:b/gcd的整数倍)

最小正整数解就是x=(x+b/gcd*n)%(b/gcd)=x%(b/gcd)

若x<=0,则x+=b/gcd

int x,y;
int g=extgcd(a,b,x,y);
x*=c/g;
b/=g;
if(b<0)b=-b;
int ans=x%b;
if(ans<0)ans+=b;
扩展欧几里得求通解、最小正整数解扩展欧几里得求通解、最小正整数解 weixin_43244265 发布了267 篇原创文章 · 获赞 14 · 访问量 7961 私信 关注
上一篇:F 最大公约数和最小公倍数问题


下一篇:N - Aroma's Search CodeForces - 1293D