CF1103B Game with modulo 做题记录

未知一个数 $a$，让你每次猜两个数 $x$ 和 $y$，若 $(x\bmod a)\ge (y\bmod a)$ 返回 x，否则返回 y。让你猜测次数少于 $60$ 次的时候猜出数 $a$。

$1\le a\le 10^9$。

首先若 $x\le a$ 且 $x\operatorname{mod} a\ge 2x\operatorname{mod} a$，那么显然 $x\le a\le2x$。

那么若找到了一个这样的 $x$，就可以在 $[x,2x]$ 中二分 $a$，若 $mid\operatorname{mod} a\ge 2mid\operatorname{mod} a$ 则记下答案向上二分，否则向下二分。

考虑怎么找出这样的 $x$，考虑倍增，从 $x=1$ 开始，若 $x\operatorname{mod} a< 2x\operatorname{mod} a$，那么让 $x\to 2x$，直到找到满足条件的 $x$ 为止。

倍增最多 $30$ 次，二分最多 $29$ 次。