AT_abc333_g [ABC333G] Nearest Fraction——数学或二分

· · 题解

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 size=8>写字试试<\font>

\frac{1}{3+\frac{1}{4+\frac{1}{2+\frac{1}{3}}}}

把这个式子倒着推上去，会得到原来的而分数。这里要求的数值要小于p,q<N。 那么右下方的数值的大小就是可以忽略到的误差。忽略的越多p,q越小。 每次求得的y/x就是前面二分得到的 k .不知道怎么证明。

疑问

为什么每次 \frac{p}{q}=\frac{a+kc}{b+kd}得到的p,q一定是互质的？