Farey Sequence

Posted by JHSN on August 26, 2017

法里数列

法里数列 (Farey sequence) $F_n$ 意为所有大小介于 $0,1$ 之间且分母不大于 $n$ 的最简分数。



数列长度

定义 $n$ 阶法里数列的长度为 $L_n$

则显然有 $L_n = L_{n-1} + \phi(n)\quad(n>1)$

所以有 $L_n = 1+\sum_{i=1}^n\phi(i)$

利用欧拉筛可以在 $O(n)$ 时间内求出



线性时间生成数列

有两种方法可以在 $O( L_n )$ 的线性时间内生成法里数列 $F_n$

① 递归法

假设我们开始有两个分数 $\frac{a}{c},\frac{b}{d}$,则有 $\frac{a}{c} < \frac{a+b}{c+d} < \frac{b}{d}$

且当 $bc-ad=1$ 时,有

Bézout's lemma 可知,$\gcd(a+b,c+d)=1$,所以我们定义下一个新分数为两分数的分子和除以两分数的分母和,该新分数介于两分数之间,且为最简分数。

定义初始条件 $\frac{a}{c}=\frac{0}{1},\frac{b}{d}=\frac{1}{1}$,结合数学归纳法易知,以上性质对于整个生成过程均成立。递归过程的终止条件为分母大于 $n$ 。

② 递推法

由上述递归法可知,按照递增顺序排列的 $F_n$ 的任意相邻两项 $\frac{a}{c}, \frac{b}{d}$ 之差为 $\frac{1}{bd}$

若已知两相邻项 $\frac{a}{c},\frac{b}{d}$,下一项为 $\frac{p}{q}$,那么显然有

设 $a+p=kb,c+q=kd$,那么这三项中的后两项之差为

因为是最接近的相邻两项,所以要使得 $d(kd-c)$ 尽量大,即取最大的 $k$,因为 $q=kd-c \leq n$,所以 $k=\left\lfloor\frac{n+c}{d}\right\rfloor$。

定义初始条件 $\frac{a}{c}=\frac{0}{1},\frac{b}{d}=\frac{1}{n}$,结合数学归纳法易知,以上性质对于整个生成过程均成立。递推过程的终止条件为 $\frac{b}{d}=\frac{1}{1}$。



例题

生成数列:[CDOJ 78]

计算长度:[CDOJ 277] [POJ 2478]




评论区加载中