本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-19 10:33:47

ABC333G

题目大意：给定整数$N$,求$gcd(p,q)=1，p，q\leq n$，使得$|r-\frac{p}{q}|$最小。

方法1：

分治，设左侧分数为$\frac{a}{b}$,右侧分数为$\frac{c}{d}$. 那么$\frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d} $

每次判断$r$与$\frac{a+c}{b+d}$的关系，缩小区间。T个点。 这个方法慢在哪里呢？ 比如$\frac{0}{1} < \frac{99}{101} < \frac{99}{100}$ 那么每次缩小的区间是很小的。 我们可以发现 $$\frac{a}{b} < \frac{a+c}{b+d}<\frac{a+2c}{b+2d}<... < \frac{c}{d} $$

方法2：

二分答案，设左侧分数为$\frac{a}{b}$,右侧分数为$\frac{c}{d}$. 那么$\frac{a}{b} < \frac{a+kc}{b+kd} < \frac{c}{d} $

再一次从过二分，找到合适得k，缩小区间。 注意数据范围本来就$10^{18}$,需要用到_int128.

方法3

//coder mhb2010: 学习来源

要想得到$\frac{p}{q}$,只要能得到$\frac{q}{p}$就可以推导出来。 例如：$N=100,r=0.31=\frac{31}{100}$那我们通过求解$\frac{100}{31}$来完成。

$$ \frac{1}{\frac{100}{31}} $$ $$\frac{1}{3+\frac{7}{31}}$$

$$\frac{1}{3+\frac{1}{\frac{31}{7}}}$$

$$ \frac{1}{3+\frac{1}{4+\frac{3}{7}}}$$ 写字试试<\font> $$
\frac{1}{3+\frac{1}{4+\frac{1}{2+\frac{1}{3}}}}
$$