P16457 [UOI 2026] Guess the Number

有一个隐藏的整数 $n$ ($1 \le n < 10^8$)，且 $n$ 不被 $10$ 整除。你的任务是找出这个数。 你可以提出如下形式的询问：选择一个整数 $x$ ($1 \le x \le 10^9$)。作为回答，你将得到数 $n \cdot x$ 的**首位数字**。 一个正整数的首位数字是指其十进制表示中最靠左的那一位数字。例如，数 $7$、$42$、$123456$ 的首位数字分别是 $7$、$4$、$1$。 你需要找出隐藏的整数 $n$。对于每个测试用例，你至多可以使用 $28$ 次询问。

第一行包含两个整数 $t$ 和 $q$ ($1 \le t \le 10^3, q=28$) —— 测试用例的数量以及每个测试用例中允许使用的最大询问次数。 ### 交互方式 在每个测试用例中，都隐藏着一个独立的数 $n$。 若要发起询问，请输出 $$\texttt{? } x$$，其中 $1 \le x \le 10^9$。 作为对询问的回应，裁判程序会输出一个整数 $d$ ($1 \le d \le 9$) —— 数 $n \cdot x$ 的首位数字。 在输出询问后，请不要忘记输出一个换行符并刷新输出缓冲区。否则，你将收到 $\tt{Time\ limit\ exceeded}$（超出时间限制）的判决。要刷新缓冲区，请使用： - C++ 中的 $\tt{fflush(stdout)}$ 或 $\tt{cout.flush()}$； - Java 中的 $\tt{System.out.flush()}$； - Pascal 中的 $\tt{flush(output)}$； - Python 中的 $\tt{stdout.flush()}$。 当你确定隐藏的数 $n$ 后，请输出 $$\texttt{! } n$$。 在此之后，如果这是最后一个测试用例，你必须终止你的程序。否则，你应当继续与下一个测试用例进行交互。 $q$ 是你的程序在一个测试用例中最多可以使用的 $\texttt{?}$ 询问次数。输出形如 $\texttt{!}$ 的答案不计入询问次数。 请注意，如果你的询问不合法，交互器会输出 $\texttt{-1}$ 并终止程序。询问在以下情形下被认为不合法： - $x$ 不满足约束 $1 \le x \le 10^9$； - 当前测试用例中的询问次数超过了 $q$； - 答案 $\texttt{! } n$ 不正确。 如果你读到了 $\texttt{-1}$，请立即终止你的程序，以便收到 $\tt{Wrong\ answer}$（答案错误）的判决，而非其他不可预期的判决。

无

考虑这个例子。假设在该例子中额外已知隐藏的数小于 $100$。 在询问 $x = 1$ 并得到回答 $1$ 后，我们得知隐藏数的首位数字是 $1$。 在询问 $x = 59$ 并得到回答 $6$ 后，我们得知隐藏数与 $59$ 的乘积的首位数字是 $6$。 在所有小于 $100$ 且不被 $10$ 整除的数中，只有 $11$ 同时满足这两个条件。因此，样例中的答案为 $11$。 ### 计分 - （$2$ 分）：$n \le 10$； - （$6$ 分）：$n \le 100$； - （$7$ 分）：$n \le 1000$； - （$8$ 分）：$n \le 10000$； - （$10$ 分）：$n$ 是完全平方数； - （$10$ 分）：$n \le 10^5$； - （$11$ 分）：$n \le 10^6$； - （$12$ 分）：$n \le 10^7$； - （$14$ 分）：$n \le 5 \cdot 10^7$； - （$20$ 分）：无额外限制。 一个解答仅当对其所属子任务中的每一个测试用例，都能在不超过 $q$ 次询问的条件下正确找出数 $n$，才算通过该子任务。 翻译由 DeepSeek V4 Pro 完成