P16409 [Algo Beat Contest 004 E] Elusive Prime

[](https://pic1.imgdb.cn/item/69b607b136d55e5b86ff6553.png)

这是一道交互题。 你需要猜测一个隐藏的素数 $p$。每次你可以询问一个整数 $a$，系统将返回勒让德符号 $\left(\frac{a}{p}\right)$ 的值，定义如下： - 如果 $p \mid a$，返回 $0$； - 否则，如果存在整数 $x$ 使得 $x^2 \equiv a \pmod{p}$，返回 $1$； - 否则，返回 $-1$。 勒让德符号是数论中的基本工具，它满足欧拉准则： $$ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} $$ ### 交互方式 你的程序需要通过标准输入输出与评测系统交互。首先，程序应开始询问，每次询问格式为： ``` ? a ``` 其中 $a$ 是一个整数，满足 $1 \le a \le 10^6$。每次询问后，评测系统会返回一个整数（$0$、$1$ 或 $-1$），你的程序应从标准输入读取该返回值。 当你确定 $p$ 后，应输出答案，格式为： ``` ! p ``` 其中 $p$ 是你猜测的素数。输出答案后，你的程序应立即结束。 你最多可以进行 **不超过 $17$ 次询问**。如果询问次数超过限制，或者答案错误，或者格式不符合要求，评测系统将判定为错误答案。 注意：每次输出后必须刷新缓冲区，例如 C++ 中使用 `cout

无

无

#### 【样例解释 #1】 样例中隐藏的素数为 $p=7$。解释： - 询问 $a=2$，返回 $1$，因为 $3^2\equiv 2\pmod{7}$。 - 询问 $a=3$，返回 $-1$，因为 $3$ 不是模 $7$ 的二次剩余。 - 询问 $a=7$，返回 $0$，因为 $7$ 被 $p$ 整除。 - 询问 $a=1$，返回 $1$，因为 $1$ 总是二次剩余。 - 最后输出答案 $7$。 #### 【数据范围】 - $3 \le p \le 10^6$，$p$ 为素数。