CF1155E Guess the Root

评委选定了一个多项式 $f(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \dots + a_k \cdot x^k$，其中 $k \leq 10$，所有 $a_i$ 都是整数，且 $0 \leq a_i < 10^6 + 3$。保证至少存在一个 $i$ 使得 $a_i > 0$。 现在，评委希望你找到一个整数 $x_0$，使得 $f(x_0) \equiv 0 \pmod{10^6 + 3}$，或者报告不存在这样的 $x_0$。 你最多可以询问 $50$ 次：每次你可以询问一个值 $x_q$，评委会告诉你 $f(x_q) \bmod (10^6 + 3)$ 的值。 注意，输出答案不计入查询次数。

无输入。

每次询问，请输出 `? x_q`，其中 $0 \leq x_q < 10^6 + 3$。评委会返回一个整数 $f(x_q) \bmod (10^6 + 3)$。如果你收到 $-1$（因为你输出了非法查询），请立即退出以避免获得其他判决。 每次输出查询后，别忘了输出换行并刷新输出缓冲区。否则，你会因为“Idleness limit exceeded”而被判失败。具体做法如下： - C++：使用 fflush(stdout) 或 cout.flush()； - Java：使用 System.out.flush()； - Pascal：使用 flush(output)； - Python：使用 stdout.flush()； - 其它语言请参考相关文档。 当你准备好输出答案时，输出 `! x_0`，其中 $x_0$ 是你找到的答案，或者 $-1$ 表示不存在这样的 $x_0$。 每个测试用例最多允许你询问 $50$ 次。 Hack 格式 进行 Hack 时，输入格式如下： 仅一行，包含 $11$ 个整数 $a_0, a_1, \dots, a_{10}$（$0 \leq a_i < 10^6 + 3$，$\max\limits_{0 \leq i \leq 10}{a_i} > 0$），表示多项式的各项系数。

第一个样例中的多项式为 $1000002 + x^2$。 第二个样例中的多项式为 $1 + x^2$。 由 ChatGPT 4.1 翻译