简要题意
有两个正整数 \(a<b\le 10^9\)，给出 \(\dfrac{a}{b}\) 的小数点后 \(19\) 位，要求还原 \(a,b\)，保证有解。
solution
一个科技：\(\texttt{Stern-Brocot tree}(SBT)\)，可以参考这个博客学习。
先给出 \(O(n)\) 找的代码：
你省（福建）省队集训 Day5 T1 题解
发布时间 2023-07-16 08:58:15作者: HaHeHyt
有两个正整数 \(a<b\le 10^9\)，给出 \(\dfrac{a}{b}\) 的小数点后 \(19\) 位，要求还原 \(a,b\)，保证有解。
一个科技：\(\texttt{Stern-Brocot tree}(SBT)\)，可以参考这个博客学习。
先给出 \(O(n)\) 找的代码：