数论详解
__O_v_O__
·
2025-02-07 08:41:01
·
算法·理论
欧几里得算法
辗转相除法
更相减损术
\gcd(a,b)=\gcd(a-b,b)
欧几里得算法
\gcd(a,b)=\gcd(b,a\bmod b)
注意到当 a>b 时 a\bmod b<\frac{1}{2}a ，所以至多递归 O(\log a) 层。
扩展欧几里得算法
求不定方程 ax+by=m 的一组整数解。
sol:
该方程有解当且仅当 \gcd(a,b)\mid m ，下面假设 d=\gcd(a,b) ，则原方程可化为 ax+by=d 。
设：
ax+by=\gcd(a, b)
bx_1+(a\bmod b)y_1=\gcd(b,a\bmod b)
假设我们已经求出 x_1 和 y_1 ，考虑得到 x 和 y 。
由欧几里得定理可知：\gcd(a,b)=\gcd(b,a\bmod b) 。
所以：ax+by=bx_1+(a\bmod b)y_1 。
又因为：
a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\times b
所以：
ax+by=bx_1+\left(a-\left\lfloor\frac{a}{b}\right\rfloor\times b\right)y_1
整理得：
ax+by=ay_1+b\left(x_1−\left\lfloor\frac{a}{b}\right\rfloor y_1\right)
对比两侧系数即得到：
x=y_1,y=x_1−\left\lfloor\frac{a}{b}\right\rfloor y_1
递归调用即可，边界是 b=0 时，此时取 x=1,y=0 。
类欧几里得算法
给定 n,a,b,c ，分别求：
\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor,\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2,\sum\limits_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor
sol:
令 f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor ，考虑 a,b,c 的关系。
两种情况递归即可，复杂度同欧几里得算法，为 O(\log n) 。
现在，我们还需要求：g(a,b,c,n)=\sum\limits_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor 和 h(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2 。
先求 g ，同样分两种情况。
若 a\ge c 或 b\ge c ：\
与 f 类似，推导出 g(a,b,c,n)=\frac{n(n+1)(2n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor+\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor+g(a\bmod c,b\bmod c,c,n) 。
若 a<c 且 b<c ：\
方便起见，设 $t=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor$，则：\
$\begin{aligned}g(a,b,c,n)&=\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^ni[i>t]\\&=\sum\limits_{j=0}^{m-1}\frac{1}{2}(t+n+1)(n-t)\\&=\frac{1}{2}\left[mn(n+1)-\sum\limits_{j=0}^{m-1}t^2-\sum\limits_{j=0}^{m-1}t\right]\\&=\frac{1}{2}\left[m n(n+1)-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\right]\end{aligned}
再求 h ，也是最复杂的一个：
若 a\ge c 或 b\ge c ：\
\frac{a}{c}\right\rfloor^2+(n+1)\left\lfloor
\frac{b}{c}\right\rfloor^2+n(n+1)\left\lfloor
\frac{a}{c}\right\rfloor\left\lfloor
\frac{b}{c}\right\rfloor\\&\ \ \ \ +2\left\lfloor
\frac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n)+2\left\lfloor
\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n)\\&\ \ \ \ +h(a\bmod c,b\bmod c,c,n)\end{aligned}
若 a<c 且 b<c ：\
同样地，令 m=\left\lfloor\frac{an+b}{c}\right\rfloor,t=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor 。\
将 n^2 写成 \left(2\sum\limits_{i=1}^ni\right)-n ，则：\
\begin{aligned}h(a,b,c,n)&=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2\\&=\sum\limits_{i=0}^n\left(\left(2\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j\right)-\left\lfloor\frac{ai+b}{c}\right\rfloor\right)\\&=\left(2\sum\limits_{i=0}^n\sum\limits_{j=0}^{\left\lfloor\frac{ai+b}{c}\right\rfloor-1}j+1\right)-f(a,b,c,n)\\&=\left(2\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^n(j+1)\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\right)-f(a,b,c,n)\\&=\left(2\sum\limits_{j=0}^{m-1}(j+1)\sum\limits_{i=0}^n[i>t]\right)-f(a,b,c,n)\\&=\left(2\sum\limits_{j=0}^{m-1}(j+1)(n-t)\right)-f(a,b,c,n)\\&=nm(m+1)-2f(c,c-b-1,a,m-1)\\&\ \ \ \ -2g(c,c-b-1,a,m-1)-f(a,b,c,n)\end{aligned}
于是 f,g,h 相互递归调用即可。
欧拉定理
基本欧拉定理
若 \gcd(a,p)=1 ，则：
a^c\equiv a^{c\bmod \varphi(p)}\pmod p
注：费马小定理即欧拉定理在 p 为质数时的特殊情况。
扩展欧拉定理
a^c\equiv\begin{cases}a^{c\bmod \varphi(p)}&\gcd(a,m)=1\\a^c&\gcd(a,m)\ne1\land c<\varphi(p)\\a^{c\bmod\varphi(p)+\varphi(p)}&\gcd(a,m)\ne1\land c\geqslant\varphi(p)\end{cases}\pmod p
例题
LOJ525
给定 k ，求出一个次数不超过 2k ，最高次项非 0 的多项式 f(x) ，使得 \forall i\in[0,k−1],f(i)\bmod k=0 。
sol:
根据扩展欧拉定理，x^{\varphi(p)}\equiv x^{2\varphi(p)}\pmod p 。
构造多项式 x^{2\varphi(p)}-x^{\varphi(p)} 即可。
相逢是问候
给定长为 n 的初始序列 a ，以及常数 c,p 。m 次操作：
sol:
记 f(a,k,p) 表示 a 经过 k 次 a=c^a 后 \bmod\ p 的值，可以递归处理。
因为 \varphi(\varphi(\cdots\varphi(p))) 至多经过 O(\log p) 层就会变成 1 ，所以这个值在 k>2\log p 时是不变的。
所以对于没有操作 2\log p 次的位置暴力修改，线段树维护：区间和，这个区间是否所有位置都修改过超过 2\log p 次询问。
复杂度 O(n\log^2 p) 。
筛法
积性函数
常见的积性函数有：
单位函数：\epsilon(n)=[n=1] 。
恒等函数：\operatorname{id}_k(n)=n^k ，当 k=1 时，简记为 \operatorname{id}(n)=n 。
常数函数：\mathbf{1}(n)=1 。
除数函数：\sigma_k(n)=\sum\limits_{d\mid n}d^k 。\sigma_0(n) 即因数个数，记为 d(n) 。\sigma_1(n) 即因数之和，记为 \sigma(n) 。
欧拉函数：\varphi(n)=\sum\limits_{d=1}^n[\gcd(d,n)=1] 。
莫比乌斯函数：
\mu(x)=\begin{cases}1&x=1\\(-1)^k&x\ 没有平方数因子，且\ x\ 的质因子个数为 k\\0&x\ 有平方数因子\end{cases}
数论分块
用于处理 \sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor 类型的和式。
常规做法是 O(n) 的。我们发现，\left\lfloor\frac{n}{i}\right\rfloor 有很多取值是相等的，考虑使用这点来优化。
重要的性质
**证明：**
对于 $i\in[1,\sqrt n]$，取值最多 $\sqrt n$ 个；对于 $i\in[\sqrt n,n]$，$\left\lfloor\frac{n}{i}\right\rfloor\le\sqrt n$，取值最多 $\sqrt n$ 个。
于是我们可以枚举每一个 \left\lfloor\frac{n}{i}\right\rfloor 取值相等的段计算，降低复杂度。
现在的问题是，我们需要对于一个 i ，求出满足 \left\lfloor\frac{n}{j}\right\rfloor=\left\lfloor\frac{n}{i}\right\rfloor 的最大的 j 是多少，根据数学推导，容易得出 j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor 。
于是我们在 O(\sqrt n) 的复杂度内解决了问题。
狄利克雷卷积
设 f(n),g(n) 是两个数论函数，则其狄利克雷卷积为 t=f\ast g ，满足：
t(n)=\sum\limits_{d|n}f(n)g\left(\frac{n}{d}\right)
一些性质
1.
\sum\limits_{d\mid n}\mu(d)=[n=1]\Leftrightarrow\mu\ast\mathbf{1}=\epsilon
证明：
设 n=\prod p_i^{k_i},n'=\prod p_i ，n 的质因数个数为 m 。
\sum\limits_{d\mid n}\mu(d)=\sum\limits_{d\mid n'}\mu(d)=\sum\limits_{i=0}^m\binom{m}{i}(-1)^i=(1-1)^m
当且仅当 m=0 即 n=1 时 \sum\limits_{d\mid d}\mu(d)=1 。
2.
\sum\limits_{d\mid n}\varphi(d)=n\Leftrightarrow\varphi\ast\mathbf{1}=\operatorname{id}
证明：
因为 \varphi 是积性函数，只需要证明 n=p^k （p 为质数）的时候 \sum\limits_{d\mid n}\varphi(d)=n 成立即可。
\sum\limits_{i=0}^k\varphi(p^i)=1+\sum\limits_{i=1}^k(p-1)p^{i-1}=p^k
则命题得证。
点乘
定义点乘运算，对于两函数 A,B ，其点乘 A\cdot B 为一个新的函数，满足 (A\cdot B)(n)=A(n)B(n) 。
当 C 是完全积性函数时，有 (A\cdot C)\ast(B\cdot C)=(A\ast B)\cdot C 。
下面是一些常见的基本和组：
杜教筛
对于数论函数 f ，杜教筛可以在低于线性时间的复杂度内计算 S(n)=\sum\limits_{i=1}^nf(i) 。
我们找一个积性函数 g ，考虑其与 f 的狄利克雷卷积：
\begin{aligned}\sum\limits_{i=1}^n(f\ast g)(i)&=\sum\limits_{i=1}^n\sum\limits_{d\mid i}g(d)f\left(\frac{i}{d}\right)\\&=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i)\\&=\sum\limits_{d=1}^ng(d)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\end{aligned}
$$\sum\limits_{i=1}^n(f\ast g)(i)-\sum\limits_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
令 $f\ast g=h$，则：
$$g(1)S(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
如果 $h$ 的前缀和是好求的，$g$ 的前缀和也是好求的，那么使用数论分块就可以递归快速求出 $S(n)$。
#### 时间复杂度
若计算 $h$ 和 $g$ 的前缀和的时间复杂度均为 $O(1)$，则杜教筛复杂度为 $O(n^{\frac{3}{4}})$。
还可以优化：我们预处理出一部分 $S(1)\sim S(m)$ 再计算。取 $m=n^{\frac{2}{3}}$ 时，复杂度为 $O(n^{\frac{2}{3}})$。
#### 筛 $\mu
因为 \mu\ast\mathbf{1}=\epsilon ，带入式子得：
\mathbf{1}(1)S(n)=\sum_{i=1}^n\epsilon(i)-\sum_{i=2}^n\mathbf{1}(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
即：
S(n)=1-\sum_{i=2}^n\mathbf{1}(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
#### 筛 $\varphi
因为 \varphi\ast\mathbf{1}=\operatorname{id} ，带入式子得：
\mathbf{1}(1)S(n)=\sum_{i=1}^n\operatorname{id}(i)-\sum_{i=2}^n\mathbf{1}(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
即：
S(n)=\frac{n(n+1)}{2}-\sum_{i=2}^n\mathbf{1}(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
### Powerful Number 筛
定义：对于正整数 $n$，记 $n$ 的质因数分解为 $n=\prod\limits_{i=1}^mp_i^{e_i}$。$n$ 是 **Powerful Number**（简称 PN）当且仅当 $\forall 1\le i\le m,e_i>1$。
#### PN 的性质
1. 所有 PN 都可以表示成 $a^2b^3$ 的形式。
**证明：**
若 $e^i$ 是偶数，则将 $p_i^{e_i}$ 合并进 $a^2$ 里；若 $e_i$ 为奇数，则先将 $p_i^3$ 合并进 $b^3$ 里，再将 $p_i^{e_i−3}$ 合并进 $a^2$ 里。
2. **$n$ 以内的 PN 有 $O(\sqrt n)$ 个。**
**证明：**
考虑枚举 $a$，再考虑满足条件的 $b$ 的个数，有 PN 的个数约等于：
$$\int_1^{\sqrt n}\sqrt[3]{\frac{n}{x^2}}\mathbf{d}x=O(\sqrt n)$$
#### PN 的求法
实际上很简单。线性筛找出 $\sqrt n$ 内的所有素数，再 DFS 搜索各素数的指数即可。
由于 $n$ 以内的 PN 至多有 $O(\sqrt n)$ 个，所以至多搜索 $O(\sqrt n)$ 次。
#### PN 筛
假设现在要求积性函数 $f$ 的前缀和 $F(n)=\sum\limits_{i=1}^nf(i)$。
我们构造出一个易求前缀和的积性函数 $g$，且对于任意素数 $p$，有 $g(p)=f(p)$。记 $G(n)=\sum\limits_{i=1}^ng(i)$。
接着，构造函数 $h$ 使得 $f=g\ast h$。根据狄利克雷卷积的性质可知 $h$ 也为积性函数，因此 $h(1)=1$。
对于素数 $p$，有 $f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)$，于是可知 $h(p)=0$。又因为 $h$ 是积性函数，所以对于任意非 PN 的数 $n$ 有 $h(n)=0$，即 $h$ 仅在 PN 处取有效值。
现在，根据 $f=g\ast h$ 有：
$\begin{aligned}F(n)&=\sum\limits_{i=1}^nf(i)\\&=\sum\limits_{i=1}^n\sum\limits_{d\mid i}h(d)g\left(\frac{i}{d}\right)\\&=\sum\limits_{d=1}^n\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}h(d)g(i)\\&=\sum\limits_{d=1}^nh(d)G\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\\&=\sum\limits_{d=1\land d\in \operatorname{PN}}^nh(d)G\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\end{aligned}
考虑计算 $h(p^c)$，两种方法：
- 推出 $h(p^c)$ 仅与 $p,c$ 有关的公式，直接计算。
- 根据 $f=g\ast h$ 有 $f(p^c)=\sum\limits_{i=0}^c g(p^i)h(p^{c−i})$，移项得 $h(p^c)=f(p^c)-\sum\limits_{i=1}^cg(p^i)h(p^{c−i})$，枚举素数 $p$ 和指数 $c$ 即可求出所有 $h(p^c)$。
总复杂度 $O(n\log n)$。
### 例题
1. **Crash 的数字表格**
$T$ 组数据，给定 $n,m$，求：
$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)$$
**sol:**
不妨设 $n\le m$，则：
$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{\gcd(i,j)}\\&=\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{d}[\gcd(i,j)=d]\\&=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij[\gcd(i,j)=1]\\&=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum\limits_{x\mid\gcd(i,j)}\mu(x)\\&=\sum\limits_{d=1}^{n}d\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij[x\mid \gcd(i,j)]\\&=\sum\limits_{d=1}^{n}d\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x)\sum\limits_{i=1}^{\lfloor\frac{n}{dx}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{dx}\rfloor}x^2ij\\&=\sum\limits_{d=1}^n\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor}dx^2\mu(x)\sum\limits_{i=1}^{\lfloor\frac{n}{dx}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{dx}\rfloor}j\end{aligned}
令 t=dx ，则原式 =\sum\limits_{t=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{t}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{t}\rfloor}j\sum\limits_{dx=t}dx^2\mu(x) 。
即是：
\sum\limits_{t=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{t}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{t}\rfloor}jt\sum\limits_{x\mid t}x\mu(x)
可以发现，t\sum\limits_{x\mid t}x\mu(x) 为积性函数，可以线性筛预处理前缀和，而前面一部分使用数论分块处理即可。
简单的数学题
给定 n ，求：
\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j)
sol:
使用 \sum\limits_{d\mid n}\varphi(d)=n 。
\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\sum\limits_{x\mid i,x\mid j}\varphi(x)\\&=\sum\limits_{x=1}^n\varphi(x)\sum\limits_{i=1}^ni[x|i]\sum\limits_{j=1}^nj[x|j]\\&=\sum\limits_{x=1}^n\varphi(x)\sum\limits_{i=1}^{\left\lfloor\frac{n}{x}\right\rfloor}ix\sum\limits_{j=1}^{\left\lfloor\frac{n}{x}\right\rfloor}jx\\&=\sum\limits_{x=1}^n\varphi(x)x^2\left(\sum\limits_{i=1}^{\left\lfloor\frac{n}{x}\right\rfloor}i\right)^2\end{aligned}
后面可以数论分块解决，现在需要快速求出 \varphi(i)i^2 的前缀和。
考虑杜教筛，令 f=\varphi\cdot\operatorname{id}^2 ，需要找出合适的 g 。
为了 (f\ast g) 求前缀和方便，由于 i\cdot\frac{n}{i}=n ，取 g=\operatorname{id}^2 ，以消掉 i 。
(f\ast g)(n)=\sum\limits_{d\mid n}\varphi(d)d^2\cdot\left(\frac{n}{d}\right)^2=n^2\sum\limits_{d\mid n}\varphi(d)=n^3
带到式子里：
\begin{aligned}g(1)S(n)&=\sum\limits_{i=1}^n(f\ast g)(i)-\sum\limits_{i=2}^n\operatorname{id}^2(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\&=\sum\limits_{i=1}^nn^3-\sum\limits_{i=2}^nn^2S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\end{aligned}
显然，n^3 与 n^2 的前缀和都可以 O(1) 求，于是问题解决。
Min_25 筛
给定积性函数 f ，其在质数的幂次的取值为 f(p^k)=p^k(p^k-1) ，求 \sum\limits_{i=1}^nf(i) 。
sol:
这里使用 PN 筛完成此题。
易得 f(p)=p(p−1)=\operatorname{id}(p)\cdot\varphi(p) ，构造 g(n)=\operatorname{id}(n)\cdot\varphi(n) 。
我们可以使用杜教筛求 g 的前缀和。具体来说，构造 f=\operatorname{id} ，则 f\ast g=\operatorname{id}^2 。
之后计算 h(p^k) 的取值：
Stern-Brocot 树
基础定义
Stern-Brocot 树是一种维护最简分数的数据结构。
逐层构造
Stern-Brocot 树可以在迭代构造第 k 阶 Stern-Brocot 序列的过程中得到。
第 0 阶 Stern-Brocot 序列由两个分数组成：
\frac{0}{1},\ \frac{1}{0}
此处的 \frac{1}{0} 严格意义上并不算是有理分数，可以理解为表示 \infty 的最简分数。
在第 k 阶 Stern-Brocot 序列相邻的两个分数 \frac{a}{b} 和 \frac{c}{d} 中间插入 \frac{a+c}{b+d} ，就得到第 k+1 阶 Stern-Brocot 序列。
前几次迭代的结果如下：
\frac{0}{1},\ \frac{1}{1},\ \frac{1}{0}
\frac{0}{1},\ \frac{1}{2},\ \frac{1}{1},\ \frac{2}{1},\ \frac{1}{0}
\frac{0}{1},\ \frac{1}{3},\ \frac{1}{2},\ \frac{2}{3},\ \frac{1}{1},\ \frac{3}{2},\ \frac{2}{1},\ \frac{3}{1},\ \frac{1}{0}
将每次迭代中新添加的分数连结成树状结构，就得到了 Stern-Brocot 树。如下图所示（图片来自 OI-wiki）：
三元组构造
另一种等价的构造方式是以三元组 (\frac{0}{1},\frac{1}{1},\frac{1}{0}) 作为根节点，且在每个节点 (\frac{a}{b},\frac{p}{q},\frac{c}{d}) 后都分别添加 (\frac{a}{b},\frac{a+p}{b+q},\frac{p}{q}),\ (\frac{p}{q},\frac{p+c}{q+d},\frac{c}{d}) 为左右子节点，就可以构造出整个 Stern-Brocot 树。
Stern-Brocot 树的每个节点记录的三元组中，实际存储的分数是位于三元组中间的分数 \frac{p}{q} ，而左右两个分数 \frac{a}{b} 和 \frac{c}{d} 是更早就出现过的分数。
性质
基本性质 ：Stern-Brocot 树是分数的二叉搜索树 ，即树上节点的中序遍历得到的分数序列是递增的。
单调性 ：Stern-Brocot 树中，每一层的分数都是单调递增 的。
最简性 ：Stern-Brocot 树构造出来的所有分数都是最简分数 。
完全性 ：Stern-Brocot 树能构造出来任意 一个正的最简分数。
这些性质的证明略去，可自行搜索。
应用
基础应用
在 Stern-Brocot 树上查找一个确定的分数 \frac{p}{q} 。
sol:
每次暴力往左或右跳的复杂度为 O(p+q) ，无法接受。
我们发现，这个方法复杂度高的原因是我们经常会连续往左或往右跳很多步。
考虑优化。观察到一次往左跳再接一次往右跳一定会让分子分母都至少变为原来的两倍，所以“拐弯”的次数是 O(\log(p+q)) 的。
于是现在我们需要快速确定每次拐弯的位置。
假设当前节点为 (\frac{a}{b},\frac{x}{y},\frac{c}{d}) ，如果 \frac{x}{y}\le\frac{p}{q} ，那么需要向右递归。设递归次数为 t ，则 \frac{x+tc}{y+td}\ge\frac{p}{q} ，解这个不等式即可。向左递归同理。
时间复杂度 O(\log(p+q)) 。
拓展应用
大部分时候，我们在树上查找的分数其实是不确定的，比如我们需要根据当前分数的值跑一个二分查找的检验算法来决定具体是往左走还是往右走。
这个时候，把刚才通过解方程来确定次数的部分改为二分连续向左或向右的次数 t 即可。复杂度 O(\log^2(p+q)) 。
例题
Fraction
若有多解，输出 $q$ 最小的一组，若仍有多解，输出 $p$ 最小的一组。
**sol:**
Stern-Brocot 树上二分的板子，连续移动次数可以列不等式解出来，复杂度 $O(T\log a)$。
2. **Farey 序列**
求分子和分母都 $\le n$ 的最简真分数组成的序列中第 $k$ 小的数。
**sol:**
在 Stern-Brocot 树上二分，剩下的就是类似二分答案地，对于一个分数 $\frac{x}{y}$，我们需要计算 $\le\frac{x}{y}$ 的分子和分母都 $\le n$ 的最简真分数数量，这个数量为：
$\begin{aligned}&\sum\limits_{i=1}^n\sum\limits_{j=1}^i[\gcd(i,j)=1]\left[\frac{j}{i}\le\frac{x}{y}\right]\\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\sum\limits_{d\mid\gcd(i,j)}\mu(d)\left[\frac{j}{i}\le\frac{x}{y}\right]\\&=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^i\left[\frac{j}{i}\le\frac{x}{y}\right]\\&=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^i\left[j\le\frac{ix}{y}\right]\\&=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left\lfloor\frac{ix}{y}\right\rfloor\end{aligned}
整除分块，\mu 的前缀和用杜教筛求，预处理 O(n^{\frac{2}{3}}) ，单次询问 O(1) 。后面是类欧，对于每个 \frac{x}{y} ，需要做 O(\sqrt n) 次类欧，每次类欧 O(\log n) 。
而 Stern-Brocot 树上二分复杂度为 O(\log^2 n) ，所以总复杂度 O(n^{\frac{2}{3}}+\sqrt{n}\log^3n) 。