Stern-Brocot 树与 Farey 序列

(Updated: )
(4 mins to read)

Stern-Brocot 树

构造

从两个最简单的分数开始： $\dfrac 01 \quad \dfrac 10$每次在相邻的两个分数$\dfrac {a}{b} \quad \dfrac{c}{d}$​中间插入一个分数$\dfrac{a+c}{b+d}$​即可

性质

  • 每一层的序列中，分数单调递增，即$\dfrac {a}{b} < \dfrac{a+c}{b+d} < \dfrac{c}{d}$这是一棵平衡树，中序遍历是有序的（建树、查找）

  • 每个分数都是最简分数

  • 可以表示出所有的最简分数，每个分数唯一

1
2
3
4
5
6
7
8
void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1)
{
  int x = a + c, y = b + d;
  // ... output the current fraction x/y
  // at the current level in the tree
  build(a, b, x, y, level + 1);
  build(x, y, c, d, level + 1);
}

Farey序列

Fi：把分母小于等于i的所有最简真分数按大小顺序排列形成的序列。可以通过SB树的方法类似构造长度：$L_i = L_{i-1} + \phi(i)$$L_i = 1 + \sum_{j=1}^n \phi(j)$分母每增大1，可以多phi(i)个最简真分数，即与i互质

求$f(x) = \dfrac{k}{x}$ 与 $g(x) = x^{\frac12}$​的交点的横坐标的最接近的分数，要求分母小于$10^5$相当于要找到最接近$k^\frac13$​的分数令初始分数为a = x-1, b = 1, c = x, d = 1然后在SB树上不断迭代靠近即可（类似二分的过程）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
ll x, k;
int main()
{
  int T;
  scanf("%d", &T);
  while(T--)
  {
    scanf("%lld", &k);
    x = 1;
    k = k*k;
    while(x*x*x<k) x++;
    if(x*x*x==k) printf("%lld/1\n", x);
    else
    {
      ll a = x-1, b = 1, c = x, d = 1, p = 0, q = 0;
      long double delta = min(x*x*x-k, k-(x-1)*(x-1)*(x-1));
      while(true)
      {
        ll x = a + c, y = b + d;
        if(y>100000) break;
        long double tmp = (long double)x*x*x/(y*y*y);
        if(fabs(tmp-k)<delta)
        {
          delta = fabs(tmp-k);
          p = x, q = y;
        }
        if(tmp>k) c = x, d = y;
        else a = x, b = y;
      }
      printf("%lld/%lld\n", p, q);
    }
  }
  return 0;
}