问题
- 求线性同余方程ax+by=c的整数解
思路
首先介绍下欧几里得算法的原理，众所周知，欧几里得算法是辗转相除法，这里给出证明：
假设a>b，证明 gcd(a,b) = gcd(a mod b,b)
设a=bk+c，c=a mod b
如果D=gcd(b,c)>gcd(a,b)，则等式 a=bk+c 右边除以D是整数，但左边除以D不是整数
如果gcd(b,c)<gcd(a,b)=D，则等式 c=a-bk 右边除以D是整数，但左边除以D不是整数
可见均矛盾，故gcd(b,c)=gcd(a,b)
拓展欧几里得算法也是基于这个递推式，根据裴蜀定理，线性同余方程ax+by=c有整数解的充要条件是c|gcd(a,b)，那么我们设a>=b，有
- ax1+bx2=1
- 根据 gcd(a,b)=gcd(b,a mod b)=1，我们有
- bx2 + (a mod b)y2=1
- 若t = a/b，有
- bx2 + (a mod b + bt -bt)y2 = 1
化简得 ay2 + b(x2-ty2) = 1
因为a mod b<b，故问题的规模可以逐步化简直至b=1，此时取一个解：xn=0, yn=1（这里也可以看出，方程有无穷多解），逐步递归即可得到答案
解决
public int[] extended(int a, int b, int c){//ax+by=c
if (a<b){a^=b;b^=a;a^=b;}
return extended(a/c,b/c);
}
public int[] extended(int a, int b){
if(b==1) return new int[]{0,1};//写成b==0 return 1,0一个道理，但为什么要多一步呢？
int[] next = extended(b,a%b);
return new int[]{next[1],next[0]-a/b*next[1]};
}
Tips
- 注意裴蜀定理中c|gcd(a,b)是充要条件，也就是说如果不符合则无解，这里为了方便不考虑这种情况，另外也不考虑a=b=c=0这种特殊情况
- gcd(a,b) * lcm(a,b) = a*b的证明：https://oi-wiki.org/math/gcd/#_5
- ax+by=1和ax≡1(mod b)完全等价，故可以用拓展欧几里得算法来求逆元，当然求逆元也有其他方式，比如线性时间复杂度中求a以内所有数的逆元，这里不展开了
- 如果不想让x或者y出现负数，可以使 x = (x+b)%b 或者 y=(y+a)%a
