CF1665D GCD Guess

这是一个交互题。 你需要猜测一个正整数 $1 \le x \le 10^9$。 在一次询问中，你可以选择两个正整数 $a \neq b$。对于这次询问，你将得到 $ \gcd(x + a, x + b) $ 的结果，其中 $ \gcd(n, m) $ 表示 $n$ 和 $m$ 的最大公约数。 为了猜出隐藏的数字 $x$，你最多可以进行 $30$ 次询问。

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 你需要猜测的整数 $x$ 满足约束条件：$1 \le x \le 10^9$。

隐藏的数字 $x$ 在交互开始前已经固定，并且不会因为你的询问而改变。 对于每个 $x$，你最多可以进行 $30$ 次询问，格式如下： - "? a b"（$1 \le a, b \le 2 \cdot 10^9$，$a \neq b$） 对于该询问，你将得到 $ \gcd(x + a, x + b) $ 的结果。 当你确定 $x$ 时，输出一行，格式如下： - "! x"（$1 \le x \le 10^9$） 之后继续解决下一个测试用例。 如果你对某个 $x$ 询问超过 $30$ 次，或者进行了非法的询问，交互器会立即终止，你的程序将收到 Wrong Answer 的判定。 每次输出询问后，不要忘记输出换行并刷新输出缓冲区。否则，你将收到 Idleness limit exceeded 的判定。刷新输出的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档。 Hack 数据 要使用 Hack，请使用如下格式的测试数据： 第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例数量。 每个测试用例的第一行包含一个整数 $x$（$1 \le x \le 10^9$），表示需要被猜测的整数 $x$。

第一个隐藏数字是 $4$，因此对于以下询问，答案分别为： "? 1 2" —— $ \gcd(4 + 1, 4 + 2) = \gcd(5, 6) = 1 $。 "? 12 4" —— $ \gcd(4 + 12, 4 + 4) = \gcd(16, 8) = 8 $。 第二个隐藏数字是 $10^9$，因此对于以下询问，答案为： "? 2000000000 1999999999" —— $ \gcd(3 \cdot 10^9, 3 \cdot 10^9 - 1) = 1 $。 这些询问仅用于帮助理解交互过程，并不足以确定真实的 $x$。 由 ChatGPT 4.1 翻译