这是一个交互问题。
我们隐藏了一个整数 $$$1 \le X \le 10^{9}$$$。您不必猜测这个数字。你必须找到这个数字的约数,甚至不需要找到确切的数字:如果你的答案的绝对误差不大于7或相对误差不大于$$$0.5$$$,那么你的答案将被认为是正确的。更正式地说,让您的答案为 $$$ans$$$,$$$X$$$ 的约数为 $$$d$$$,那么如果以下两个条件至少之一为真,则您的答案将被视为正确:
- $$$| ans-d| \le 7$$$;
- $$$\frac{1}{2} \le \frac{ans}{d} \le 2$$$。
您最多可以进行 $$$22$$$ 查询。一个查询由一个整数 $$$1 \le Q \le 10^{18}$$$ 组成。作为响应,您将得到 $$$gcd(X, Q)$$$ — $$$X$$$ 和 $$$Q$$$ 的最大公约数。
数字 $$$X$$$ 在所有查询之前都是固定的。换句话说,交互器不具有适应性。
我们把猜测$$$X$$$的约数的过程称为游戏。在一项测试中,您必须玩 $$$T$$$ 独立游戏,即猜测 $$$X$$$ 的 $$$T$$$ 独立值的除数 $$$T$$$ 次。
输入
输入的第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 游戏数量。
互动
要进行查询,请打印一行“? Q” ($$$1 \le Q \le 10^{18}$$$)。之后读取一个整数$$$gcd(X, Q)$$$。在一场游戏中,此类查询的数量不得超过 $$$22$$$。
如果您确信自己已经足够精确地算出 $$$X$$$ 的约数个数,则可以以“! ans”格式打印您的答案。 $$$ans$$$ 必须是整数。如果这是最后一场比赛,则必须终止程序,否则必须立即开始下一场比赛。请注意,交互器不会打印任何内容来响应您打印的答案。
打印查询后,不要忘记输出行尾并刷新输出。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请使用以下格式:
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 游戏数量。
接下来的 $$$T$$$ 行都包含一个整数 $$$X$$$ ($$$1 \le X \le 10^{9}$$$) — 隐藏数字。
因此该示例具有以下形式
示例
输入 #1
2 1 1 1 1024 1048576 4194304
输出 #1
? 982306799268821872 ? 230856864650023977 ? 134690134760714371 ! 5 ? 1024 ? 1048576 ? 1073741824 ! 42
注意
为什么查询数量限制为22?也许问题的作者是泰勒·斯威夫特的粉丝。
让我们看一下这个例子。
在第一场比赛中,$$$X = 998\,244\,353$$$ 被隐藏。很难猜到这一点,对吧?这个数字是素数,所以它的约数是2。解决方案进行了几次随机查询,所有的响应结果都是1(奇怪的是,甚至三个随机数中没有一个能被$$$998\,244\,353$$$整除)。假设隐藏的数字没有很多除数是很困难的,因此解决方案的答案是 5。为什么不呢?这个答案将被认为是正确的,因为 $$$| 5 - 2 | 5 - 2 = 3 \le 7$$$。
在第二个游戏中 $$$X = 4\,194\,304 = 2^{22}$$$ 被隐藏,它有 23 个约数。该解决方案已发出查询 $$$1024 = 2^{10}$$$, $$$1\,048\,576 =2^{20}$$$, $$$1\,073\,741\,824 = 2^{30}$$$ 并获得响应 $$$1024 = 2^{10}$$$, $$$1\,048\,576 =2^{20}$$$, $$$4\,194\,304 = 2^{22}$$$。然后这个解决方案就完全混乱了,并回答了生命、宇宙和一切的终极问题的答案。这个答案将被认为是正确的,因为 $$$\frac{1}{2} \le \frac{42}{23} \le 2$$$。