扩展欧几里德算法复习
NOI 前发点比较无聊的东西。
感觉这么多公式会让人看着想睡觉，也不知道怎么解决。
求不定方程 (Ax+By=C(A,B,Cin mathbb Z)) 的所有整数解。
(|A|,|B|,|C|le 10^{18})
裴蜀定理：这个方程有解当且仅当 (gcd(A,B)|C) 。
证明：(gcd(A,B)
ot|C) 时原方程无解是显然的。对于 (gcd(A,B)|C) 的情况一定有解，接下来构造解。
-
当 (A=B=0) 时，必有 (C=0)，显然任何整数对 ((x,y)) 都属于解集。
-
当 (A=0,B e 0) 时，(x) 可以是任意整数，而 (y=C/B)。(A e 0,B=0) 同理。
-
当 (A,B) 都非 (0) 时，可不妨假设 (A>0,B>0)（其他情况的解都可以取反得到）。
设 (d=gcd(A,B),a=A/d,b=B/d,c=C/d)。
那么 (ax+by=c) 的解就是我们想要的。注意到这时候 (a,b) 互质了。
-
当 (c=0) 时，因为 (a,b) 互质，((x,y)=(kb,-ka),kin mathbb Z)。
-
当 (c e 0) 时，考虑两个不同的解 ((x_0,y_0)) 和 ((x_1,y_1))，有
(ax_0+by_0=c)
(ax_1+by_1=c)
相减得
(a(x_0-x_1)+b(y_0-y_1)=0) 。根据 (c=0) 的情况，((x_0-x_1,y_0-y_1)=(kb,-ka),kin mathbb Z)。
因此如果我们有了一组特解 ((x_0,y_0))，那么就有 ((x,y)=(x_0+kb,y_0-ka),kin mathbb Z)。
那么现在的关键是得到 ((x_0,y_0))。尝试先构造 (ax+by=1) 的一组解，再乘上 (c)。这部分就使用了经典的扩展欧几里德算法了。
假设我们已经构造出了 (bx'+(amod b)y'=1) 的解 ((x',y'))。
(bx'+(a-lfloor a/b floor b)y'=1)
(ay'+b(x'-lfloor a/b floor y')=1)我们发现 (x=y',y=x'-lfloor a/b floor y')。
求 ((x',y')) 的话，往下递归即可。边界是 (b=0) 的情况，此时必有 (a=1)，那么令 (x=1,y=0) 即可（用这个解是为了方便，也是为了不爆精度）。
-
那么我们就做完了。
还有一个问题，为什么这样写不会爆精度。也就是说求出来的那个特解最大会是多少。
关于这个，有一位高级科学家给出了很高级的界，在这里。可惜我没有那么高级，我觉得够用就好。
所以我只证明这样子求出来的 (ax+by=1) 的那个解 ((x,y)) 会满足 (max(|x|,|y|)le max(a,b))。
不妨假设 (age b>0)（(a<b) 的话，第一次迭代只相当于把 (a) 和 (b) 交换，(x) 和 (y) 也交换）。其实这时候有 (|x|le b,|y|le a)。我们证明它。
当 (amod b=0) 时，必然有 (b=1)。经过简单模拟可以发现求出的 (x=0,y=1)，必满足条件。
当 (amod b e 0) 时，有 (bge amod b >0)。如果已经证明对于方程 (bx'+(amod b)y'=1) 的解 ((x',y')) 满足 (|x'|le amod b,|y'|le b)，我们可以推出所得到的 (ax+by=1) 的解也符合条件，如下：
首先不管怎样，(x') 和 (y') 不能全都为正数，但是必有一个正数，这是显然的。并且当 (x'>0,y'le 0) 时，(xle 0,y>0)；而 (x'le 0,y'>0) 时，(x>0,yle 0)。
由此容易得到，(|x|=|y'|,|y|=|x'|+lfloor a/b floor|y'|)。
由 (|x'|le amod b,|y'|le b) 得，
(|x'|le a-lfloor a/b
floor b)
(lfloor a/b
floor|y'|le lfloor a/b
floor b)
两式子相加即得 (|y|=|x'|+lfloor a/b floor|y'|le a)，同时 (|x|=|y'|le b)。
由数学归纳法，我们证完了。