### Ambiguous Numbers题号：198 难度： 80 中英对照

A best approximation to a real number x for the denominator bound d is a rational number r/s (in reduced form) with sd, so that any rational number p/q which is closer to x than r/s has q > d.

Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. 9/40 has the two best approximations 1/4 and 1/5 for the denominator bound 6. We shall call a real number x ambiguous, if there is at least one denominator bound for which x possesses two best approximations. Clearly, an ambiguous number is necessarily rational.

How many ambiguous numbers x = p/q, 0 < x < 1/100, are there whose denominator q does not exceed 108?

### Solution

Farey数列是一个在区间$[0,1]$的最简分数序列，且容易看出除了$0$和$1$以外都是真分数，这个序列包括所有分母不超过给定数字$k$的最简分数且从小到大排列，记为$F[k]$，为表述方便，$0$和$1$一般表示为$0/1$和$1/1$，例如： $$F[1]=\{0/1,1/1\}$$ $$F[2]=\{0/1,1/2,1/1\}$$ $$F[3]=\{0/1,1/3,1/2,2/3,1/1\}$$ $$F[4]=\{0/1,1/4,1/3,1/2,2/3,3/4,1/1\}$$ $$F[5]=\{0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1\}$$ $$……$$ Farey数列有三个很重要的基本性质： 1. $a/b$和$c/d$是某个$F[k]$数列的相邻两项，当且仅当$bc-ad=1$ 2. 若$bc-ad=1$，则处于$a/b$和$c/d$之间的分母最小的分数是$(a+c)/(b+d)$，且不能约分，且是唯一的，即这个区间中不存在其他以$b+d$为分母的分数 3. 若$a/b< c/d< e/f$是某个$F[k]$数列的连续三项，则$c/d=(a+e)/(b+f)$ $x$为一个两可数当且仅当对于某个$a/b$和$c/d$，$x-a/b=c/d-x$，于是解得 $$x=(ad+bc)/(2bd)$$ 于是就可以从数列$\{0/1,1/50\}$开始，按照Farey数列的生成规则，用递归搜索所有$a/b$和$c/d$，计算$x$，其中$b$、$d$和$x$的分母都不超过$10^8$，且$x< 1/100$即可。

### Code

import java.util.ArrayDeque;

public final class p198 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public String run() {

final long size = 100000000;
final long boundn = 1, boundd = 100;
ArrayDeque<Long> list = new ArrayDeque<Long>();
long leftn = 0, leftd = 1; // Farey number on the left
long rghtn = 1, rghtd = 50; // Farey number on the right
long count = 0;
while (true) {
long ambigd = 2 * leftd * rghtd; // get ambiguous number in this
// interval
if (ambigd <= size) {
long ambign = leftd * rghtn + leftn * rghtd;
if (ambign * boundd < boundn * ambigd)
count++; // count it if it is in range
long medn = leftn + rghtn, medd = leftd + rghtd; // split
// interval
// by
// mediant
if ((medn * boundd <= boundn * medd)) {
list.push(leftd);
list.push(leftn); // save lhs interval
leftn = medn;
leftd = medd; // use rhs interval
} else {
rghtd = medd;
rghtn = medn; // use lhs interval
}
} else { // bottomed out
if (list.isEmpty())
break; // get next interval, if any
rghtn = leftn;
rghtd = leftd;
leftn = list.pop();
leftd = list.pop();
}
}
return count+"";
}

}
52374425
3710ms