CF1355F Guess Divisors Count

这是一个交互题。 我们有一个隐藏的整数 $1 \le X \le 10^{9}$。你不需要猜出这个数本身。你需要找出这个数的约数个数，甚至不需要精确找出：只要你的答案的绝对误差不超过 7，或者相对误差不超过 $0.5$，你的答案就会被认为是正确的。更正式地说，设你的答案为 $ans$，$X$ 的约数个数为 $d$，那么只要以下两个条件之一成立，你的答案就被认为是正确的： - $|ans - d| \le 7$； - $\frac{1}{2} \le \frac{ans}{d} \le 2$。 你最多可以进行 $22$ 次询问。每次询问你可以给出一个整数 $1 \le Q \le 10^{18}$。作为回应，你会得到 $gcd(X, Q)$——即 $X$ 和 $Q$ 的最大公约数。 数 $X$ 在所有询问前就已确定。换句话说，交互器不是自适应的。 我们把猜测 $X$ 的约数个数的过程称为一局游戏。在一次测试中，你需要进行 $T$ 局独立的游戏，也就是说，需要对 $T$ 个独立的 $X$ 分别猜测其约数个数。

输入的第一行包含一个整数 $T$（$1 \le T \le 100$），表示游戏的局数。

每次询问时，输出一行 "? Q"（$1 \le Q \le 10^{18}$）。之后读取一个整数 $gcd(X, Q)$。在每局游戏中，你最多可以进行 $22$ 次这样的询问。 如果你确信已经足够精确地得出了 $X$ 的约数个数，可以输出 "! ans" 的格式，其中 $ans$ 必须是整数。如果这是最后一局游戏，你需要终止程序，否则应立即开始下一局游戏。注意，交互器在你输出答案后不会有任何回应。 每次输出询问后不要忘记输出换行并刷新输出缓冲。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档。 Hacks 用于 hack 的输入格式如下： 第一行包含一个整数 $T$（$1 \le T \le 100$），表示游戏的局数。 接下来的 $T$ 行，每行包含一个整数 $X$（$1 \le X \le 10^{9}$），即隐藏的数。 例如： ``` 2 998244353 4194304 ```

为什么询问次数的限制恰好是 22 次？也许出题人是 Taylor Swift 的粉丝。 让我们看看例子。 在第一局游戏中，隐藏的 $X = 998\,244\,353$。要猜出这个数很难，对吧？这个数是质数，所以它的约数个数是 2。解题者进行了几次随机询问，所有回应都是 1（很奇怪，居然没有一个随机数能被 $998\,244\,353$ 整除）。可以合理地假设隐藏的数的约数个数不会很多，于是解题者回答了 5。为什么不呢？这个答案会被认为是正确的，因为 $|5 - 2| = 3 \le 7$。 在第二局游戏中，隐藏的 $X = 4\,194\,304 = 2^{22}$，它有 23 个约数。解题者依次询问了 $1024 = 2^{10}$，$1\,048\,576 = 2^{20}$，$1\,073\,741\,824 = 2^{30}$，得到了 $1024 = 2^{10}$，$1\,048\,576 = 2^{20}$，$4\,194\,304 = 2^{22}$ 的回应。然后解题者彻底懵了，回答了生命、宇宙以及一切的终极答案。这个答案会被认为是正确的，因为 $\frac{1}{2} \le \frac{42}{23} \le 2$。 由 ChatGPT 4.1 翻译