P16409 [Algo Beat Contest 004 E] Elusive Prime

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

This is an interactive problem. You need to guess a hidden prime $p$. Each time, you may query an integer $a$, and the system will return the value of the Legendre symbol $\left(\frac{a}{p}\right)$, defined as follows: - If $p \mid a$, return $0$. - Otherwise, if there exists an integer $x$ such that $x^2 \equiv a \pmod{p}$, return $1$. - Otherwise, return $-1$. The Legendre symbol is a basic tool in number theory, and it satisfies Euler's criterion: $$ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} $$ ### Interaction Your program must interact with the judge through standard input and output. First, your program should start querying. Each query should be in the following format: ``` ? a ``` Here, $a$ is an integer satisfying $1 \le a \le 10^6$. After each query, the judge will return an integer ($0$, $1$, or $-1$), and your program should read this value from standard input. When you are sure about $p$, output the answer in the following format: ``` ! p ``` Here, $p$ is the prime you guessed. After outputting the answer, your program must terminate immediately. You may make **at most $17$ queries**. If the number of queries exceeds the limit, or the answer is wrong, or the format does not meet the requirements, the judge will consider it a wrong answer. Note: After each output, you must flush the buffer, for example, use `cout

N/A

N/A

#### Sample Explanation #1 In the sample, the hidden prime is $p=7$. Explanation: - Query $a=2$, and it returns $1$, because $3^2\equiv 2\pmod{7}$. - Query $a=3$, and it returns $-1$, because $3$ is not a quadratic residue modulo $7$. - Query $a=7$, and it returns $0$, because $7$ is divisible by $p$. - Query $a=1$, and it returns $1$, because $1$ is always a quadratic residue. - Finally, output the answer $7$. #### Constraints - $3 \le p \le 10^6$, and $p$ is prime. Translated by ChatGPT 5