推导

假设,我们已经求出有一对x,y满足ax+by=gcd(a,b)。

我们想要求最小非负整的x,那么必须要减去一个能减的 最大值,我们设减去一个D,则方程变为: a(x-D)+by+aD=gcd(a,b)

整合一下： a(x-D)+b(y-aD/b)=gcd(a,b)

我们知道,gcd(a,b)是整数,我们假设aD/b不为整数。 则对应的’y’(现在的y)为小数,不成立,所以aD/b是整数 即aD%b=0。

又因为aD%a=0,所以aD一定而且只需是a,b的倍数,所以aD=k(Lcm(a,b))=abk/gcd(a,b)

两边同时除a

D=k*b/gcd(a,b)//即D为b/gcd(a,b)的k倍,k为任意整数

我们要使D尽可能大,则k也要尽可能大所以可以表达为代码: 

int D=b/gcd(a,b)//当k==1时D的值 while(x>=0) { x-=D; } if(x<0){ x+=D; }

不过,这样明显浪费时间,于是我们想到了用取摸代替减法： 

x%=D; if(x<0){ x+=D; }

另类整合if: 

x=(x%D[保证x变为最小正或最大负]+D)%D