6719. 【2020.06.12省选模拟】T2 Module

题目

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


正解

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

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

现在写成这样:xy=a(modP)\frac{x}{y}=a \pmod Pyx​=a(modP)
化一下就是x=aykPx=ay-kPx=ay−kP,两边除以PyPyPy就是xPy=aPky\frac{x}{Py}=\frac{a}{P}-\frac{k}{y}Pyx​=Pa​−yk​
x1e9x\leq 1e9x≤1e9的解只有一个,具体怎样理解可以结合上面的性质。
由于PyPyPy太大(大于1e181e181e18)了,趋近于000。于是我们要做的就是找到ky\frac{k}{y}yk​,使其尽量逼近aP\frac{a}{P}Pa​。

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

此外还有隔壁的爆标算法,推一波类欧。
具体是解这样的不等式:laxmod  prl \leq ax \mod p\leq rl≤axmodp≤r,类欧推一下。

上一篇:CF1029E Tree with Small Distances


下一篇:HTTP权威协议笔记-8.集成点:网关、隧道及中继