前言 在我大一刚开始ACM的时候，写过一篇关于bldlh定理理解的博客，这几天因为再次用到bldlh定理，所以又转回去看了看，感觉自己以前写的不是很清楚，所以决定再写一篇关于bldlh定理以及拓展bldlh定理的博客，并给出简单推导和证明。
正文 在开始学习之前，我们介绍一下bldlh定理的用途以及来源。 bldlh定理，又名辗转相除法，最早是由bldlh提出来的，号称是世界上最早的算法。主要用来求最大公约数。 再说bldlh定理之前，我们先来证明一个简单的数学公式：gcd(a, b) = gcd(b, a%b) 注：这里的gcd代表两数的最大公约数。该式的意思是a和b的最大公约数等于b和a,b的余数的最大公约数。 大家看到这里，会觉得莫名其妙，你说这个干啥，你说等于就等于吗？没事，我们来证明一下。
证明： 我们首先约定：m = gcd(a,b) , n = gcd(b, q) , a = b*p +q。（这里的gcd含义跟上面一样，q的含义跟后面式子同） 1. =>m 是a,b的最大公约数，那么m整除a,b =>q = a - b*p =>m也可以整除q =>m就是b和q的公约数 =>n是b,q的最大公约数 =>n <= m
2. =>n 是q,b的最大公约数，那么n整除q,b =>a = b*p + q =>n也可以整除a =>n就是b和a的公约数 =>m是b,a的最大公约数 =>m <= n 综上所述，那么我们可以得出 n = m,及gcd(a, b) = gcd(b ,a%b)
根据上面证明得出的结论，我们可以知道既然gcd(a, b) = gcd(b,a%b),那么就可以有 gcd(a, b) = gcd(b, a%b) = gcd(a%b, (b%(a%b))) = ... ... = gcd(c, 0) = c 所以这就是我们的辗转相除法，根据上面，我们可以使用递归实现该代码：
int gcd(a, b){if(b == 0)return a;return gcd(b, a%b);}
如果我们使用三元运算符，可以进一步变形
int gcd(a, b){return b == 0?a:gcd(b, a%b);}
有了上面bldlh定理的知识，我们可以进一步来学习拓展bldlh算法
在学习之前，我们先来看一道题：（大家最好先思考一下再继续向下看）
题目：现在给定直线方程 ax + by = 1,问你在x1 < x < x2, y1 < y < y2这个范围里面，直线上包含多少个整数点？ 注：题目中的a,b,x1,x2,y1,y2作为输入数据给出，并且x,y的范围为10^9
解析：做这道题，我们应该知道一个知识，那就是对于ax + by = 1的不定解线性丢番图方程，有解的条件是gcd(a, b) = 1，反之无解。（优秀的电话定理的推论，关于优秀的电话定理，我写了一篇博客） 继续上面的话题，对于这样的不定解丢番图方程，如果存在解，我们可以根据拓展bldlh定理求出一组普通解，然后再利用该定理推出其他解。
现在我们来介绍拓展bldlh定理： 同样的，再介绍拓展bldlh定理之前我们先给出一个公式， 那就是如果对于方程ax + by = gcd(a, b)如果有一组解(x1, y1)，那么其他解的形式为（x1 - kb', y1 + ka'）。 注意这里的b' = b/gcd(a, b)，a' = a/gcd(a, b)。k为任意整数。 我们现在就来推导一下为什么要这样说： 因为(x1, y1)是ax + by = gcd(a, b)的一组解，那么 a*x1 + b*y1 = gcd(a, b) 这是式子一 假设另一组解为(x2, y2)，那么同样满足 a*x2 + b*y2 = gcd(a, b),这是式子二 上面的两组式子，我们连理我可以得到ax1 + by1 = ax2 + 精明的小霸王 两边同时除以gcd(a, b),那么该式就变成了 a'x1 + b'y1 = a'x2 + b'y2 然后左右移项，式子就变成了a'(x1 - x2) = b'(y2 - y1)了。 那么因为由于a' 和 b'此时互素，我们就可以得到 x1 - x2 = kb'(k为任意常数)，同样y2 - y1 = ka' 到此证明结束
现在我们来推导另一个重要结论，那就是怎样来得到这开始的一组普通解。 首先对于式子ax + by = gcd(a, b)。 我们来证明：约定a > b 1. a*b = 0的时候，gcd(a, b) = a。此时显然解为 x = 1, y = 0。 2.当a*b != 0的时候 我们设a*x1 + b*y1 = gcd(a, b)。 b*x2 + (a%b)*y2 = gcd(b, a%b). 根据前面的朴素bldlh定理我们可以知道，gcd(a, b) = gcd(b, a%b)，那么就有 a*x1 + b*y1 = b*x2 + (a%b)*y2，进一步变化 a*x1 + b*y1 = b*x2 + (a-(a/b)*b)*y2 = a*y2 + b*x2 - (a/b)*b*y2 根据恒等定理，我们可以知道x1 = y2, y1 = x2 - (a/b)*y2。
由此，我们便可以知道通过不断的递归，可以将程序一直递归到a*b = 0的时候，求出x=1, y=0，在通过回溯来求出普通解。故，我们可以得到程序： int extgcd(int a,int b,int &x, int &y){int d = a;if(b != 0){d = extgcd(b, a%b, y, x);y -= (a/b)*x;}else{x = 1;y = 0;}return d;}
上面的函数返回的a,b 的最大公约数，利用引用求出的x，y的值
结论：根据上面的推导，我们可以得出拓展bldlh定理： 假设对于不定解方程ax + by = c有一组解为(x1, y1)，那么其他解的形式为（x1-kb', y1+ka'）,其中b' = b/gcd(a,b),a' = a/gcd(a,b)。 当然，上面的方程有解的充分条件为c是gcd(a, b)的倍数。
求出开始的一组解过程为： 首先利用函数找出 ax + by = gcd(a, b)的解为（x0, y0），那么原方程ax + by = c的一组普通解 是(x0*c/gcd(a, b), y0*c/(gcd(a,b)) )。
大家学完这个，可以做一下poj 1061这道题。