题目

这题是交互题……
oj现在不支持交互题……
所以直接在这讲讲题目大意吧。
有个分数$\frac{x}{y}$yx​，你可以询问一个质数$P$P，可以得到$\frac{x}{y}$yx​在模$P$P意义下的值。
最多可以询问$5$5次。
数字的范围都在$[1,1e9]$[1,1e9]
多组数据，数据最多$10^5$105组。

---

正解

只需要询问两个质数$P_1=1e9+7$P1​=1e9+7和$P_2=1e9+9$P2​=1e9+9，通过中国剩余定理可以求出$\frac{x}{y}$yx​在模$P_1P_2$P1​P2​意义下的值。
这时候$\frac{x}{y}$yx​是唯一确定的。

证明考虑如果有$\frac{x_1}{y_1}$y1​x1​​和$\frac{x_2}{y_2}$y2​x2​​不相等但在模意义下相等，那么$x_1y_2\equiv x_2y_1 \pmod {P_1P_2}$x1​y2​≡x2​y1​(modP1​P2​)
由于$P_1P_2>1e18$P1​P2​>1e18，$x_1y_2,x_2y_1\leq1e18$x1​y2​,x2​y1​≤1e18，所以如果它们模意义下相等，那么它们实际上也相等。
矛盾。

现在写成这样：$\frac{x}{y}=a \pmod P$yx​=a(modP)
化一下就是$x=ay-kP$x=ay−kP，两边除以$Py$Py就是$\frac{x}{Py}=\frac{a}{P}-\frac{k}{y}$Pyx​=Pa​−yk​
$x\leq 1e9$x≤1e9的解只有一个，具体怎样理解可以结合上面的性质。
由于$Py$Py太大（大于$1e18$1e18）了，趋近于$0$0。于是我们要做的就是找到$\frac{k}{y}$yk​，使其尽量逼近$\frac{a}{P}$Pa​。

题解做法：
在Stern-Brocot Tree上二分。
直接一个一个走可能会时间超限。发现拐点有$O(\lg 1e9)$O(lg1e9)个，于是走的过程中可以二分它往某个方向最多走多少步。

此外还有隔壁的爆标算法，推一波类欧。
具体是解这样的不等式：$l \leq ax \mod p\leq r$l≤axmodp≤r，类欧推一下。