扩展欧几里得算法
今天开始学习数论方面的算法.这部分在 NOIP 中并不常出现,即使出现了也不会像高联这么难(...).
什么是扩展欧几里得算法
所谓欧几里得算法,实际上就是辗转相除法 -  - 求两个数最大公约数的一种高效算法.而扩展欧几里得算法则是来源于于一类方程的解决:
$$ax+by=gcd(a,b)$$
这有点像是裴蜀定理的一般形式.和裴蜀定理类似,这类方程也有无数多个整数解.如何高效率地求得它的一组特解呢?
procedure gcd_ex(a, b: longint; var d: longint; var x, y: longint);
if b = 0 then
d := a;
x := 1;
1    g