先任意询问两个不同的素数，然后 CRT 合并，得到 $q=pX\bmod M$，我们要求 $1\le p,q\le 10^9$，即找到 $p$ 使得 $1\le p \le 10^9$ 且 $pX\bmod M\le 10^9$。二分 $p$，则需要检查是否有不超过 $L$ 的 $p$，注意到这等价于 $\lfloor \frac{pX-10^9-1}{M}\rfloor\ne \lfloor\frac{pX}{M}\rfloor$，故可以用类欧几里得算法求出等号两边的和并比较。时间复杂度 $O(t\log^2p)$。

还有一种 $O(t\log p)$ 的做法：要求的即为 $\min\{i\ge 0\mid 1\le iX\bmod M\le 10^9\}$，考虑求 $\min\{x\ge 0\mid l\le ax\bmod p\le r\}$，有

• 当 $a=0$ 时，若 $l=0$ 则 $x=0$，否则无解。
• 当 $a\lceil l/a\rceil\le r$ 时，$x=\lceil l/a\rceil$。
• 否则设 $p=ka+b\pod{0\le b < a}$，则 $l\le ax-(ka+b)y\le r$，$l\le a(x-ky)-by\le r$，若确定了 $y$，则 $x=\lceil(by+l)/a\rceil+ky$，而 $y$ 满足 $a-r\bmod a\le by\bmod a\le a-l\bmod a$，因此递归求解即可。