转自：http://blog.sina.com.cn/s/blog_4d88e9860100fc0a.html
说到这个数列，就要谈到互质的概念，这个性质导致了这个数列及那个SB(-_-)树的优美的特性。在正式讲Farey前，先考虑一个问题：给出任意一个实数（有理数、无理数），与其最相近的分数是多少。对于一个有理数，我们自然知道有唯一的分数相对应，而无理数则是无限的接近，无法相等，那么怎么找这个分数呢？看完了farey，一切豁然开朗。
来看这样一棵树： 
发现其特性了吗，比如1/4，是(0+1/1+3)也就是说是上一层中与其“相邻”的2个分数，分别分子加分子，分母加分母形成。对于每一个farey数列，比如F7=0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1 这个数列的分数是从小到大排列的，并且分数m/n gcd(m,n)=1.
为什么呢，首先它是有序的，因为每一个分数由上一次相邻的分数产生，并“插入”当前一层，那么m/n<=(m+m’)/(n+n’)<=m’/n’,所以产生的分数必然是有序的。
对于gcd(a,b)=1=>ax-by=1 如果m/n m’/n’可以得到m’n-m’n=1，那么(m+m’)n-m(n+n’)=1 m’(n+n’)-(m+m’)n’=1，而对于数列的最初1*1-0*0=1，所以数学归纳法可得，在上图的树中的相邻的分数产生的分数的分子分母是互质的，并且有序的。
http://202.120.80.191/problem.php?problemid=2649 这个题，是问给出一个实数，其最邻近的分数是多少，因为有可能越逼近其分母越大，所以有一个数L为分母的上限。首先观察这个SB树，那么很容易想到最简单的方法（伪代码）：R为那个实数
while(1)
{
mid(l.zi+r.zi,l.mu+r.mu);
if(mid.mu>L)
{
if((R-l(l))<(l(r)-R))return l;
else return r;
}
if(mid<R)l=mid;
else if(mid>R)r=mid;
else return mid;
}
但是再观察一下这棵树，原来很开心，这是给出一个区间二分找，速度很快的应该，但是其实不然，比如我给出1/L，那么我需要找L次，复杂度为o(n)的，深度太深了。怎么解决这个问题呢，haozi的方法是如果一个大区间确定了m/n m’/n’，那么如果在这个区间中是要往左子树走x次，那么其实就是(m+xm’)/(n+xn’)，而如何确定这个x就是列一个不等式(m+xm’)/(n+xn’)=R，解出即可，这样连续要走很多次就被锁的很小，也许会疑惑如果连续走的次数很少呢，但是要想到的是如果连续的次数少深度必然也小，可以解决了。
而我的想法是导致很坏的情况一个原因是因为初始的上下界太大，都是0/1 1/1，有没有办法找到一个更精确的界限呢。首先如果R*L取整后，[R*L]/L（化为最简）是一个下界，那么我只要在这个SB树中找到相对应的比这个分数的分数，但是怎么找呢。在上面介绍farey数列的时候说到一个性质，就是如果m/n m’/n’如果是相邻的，就有m’n-mn’=1，熟悉吧，这个不就只要扩展欧几里得就可以解决了嘛！！！于是从[R*L]/L可以推得相应的上界r，如果r>R，我可以断定R就在这个([R*L]/L,r)区间中，因为farey是有序数列，并且随着树的层数越深，只会越密而不会跳。但是问题还没有解决，因为这样的r很有可能是<R的，那怎么办？其实很简单如果r<R,那么我其实找到了一个新的上界l,l=r,而r再由扩展欧几里得算出，知道找到一个区间(l,r)包含了R，于是问题也可以解决。回过头来想，为什么要在SB树上，并且要用扩展欧几里得来求上界呢，不能任意取两个界限，然后不断二分，其原因就是如果是任意的分数，相加后并不能保证分子和分母互质，那么就确信什么时候已经是在L的限制中最相近的分数了，在SB树中，因为互质，所以产生的分数分母必然只会递增，当发现分母超过L时即可退出，而任意时会在分母大于L后又会变小。
还有一个题也是farey数列的，就是2008年合肥赛区的现场赛的
Rational Number Approximation http://acm.uva.es/archive/nuevoportal/
这个题意思是给出一个分数a/b，求出一个包含这个分数的最小区间，要最小，必然是比a/b小的尽量大，比a/b大的尽量小。我的方法就是已知a/b，可以得到在SB树中相邻的左和右，这个就是2个区间了，再接下来找的方法就是和上面一题一样了，注意一些细节即可。