P13746 [NWERC 2024] Hash Collision

出于安全考虑，TU Delft 决定在大量房间的门上安装带有数字键盘的锁。每个房间将拥有自己的密码。负责搭建存储所有密码的服务器的任务交给了 Harry 和 Sharon。 :::align{center}  图片剪影来自 [pxfuel.com](https://www.pxfuel.com/en/free-photo-jrhmi)，可自由使用。 ::: 由于在网络安全课上认真听讲，他们知道密码在存储前应该经过哈希函数处理，最好多次处理。 Sharon 想出了一个巧妙的主意：让房间号作为密码经过哈希函数的次数。这样，即使两个房间碰巧有相同的密码，它们最终的哈希值也不一定相同。然而，他们发现对于某些房间号和密码的组合，哈希值恰好等于原始密码，这带来了安全隐患。 Harry 不甘示弱，也提出了自己的想法：交换角色，也就是说，让密码作为哈希函数作用于房间号的次数。换句话说，如果 $c$ 是密码，$r$ 是房间号，则哈希值为 $f^c(r) = \underbrace{f(\cdots f(}_{c~\mathrm{次}}r)\cdots)$。 经过一番思考，Sharon 声称，无论函数 $f$ 是什么，总会存在某些房间号和密码，使得哈希值等于密码，即 $f^c(r) = c$。事实上，Sharon 认为即使不知道 $f$ 的全部细节，找到这样的一对数也不会太难。 Sharon 的轻描淡写让 Harry 很生气，他认为 Sharon 只是嫉妒他的想法。两人争论不休，最终 Harry 决定让 Sharon 证明她的观点：他写了一个程序，允许查询，返回给定 $c$ 和 $r$ 下的哈希值 $f^c(r)$，其中 $f$ 是他选择的一个秘密哈希函数。哈希函数接受任意 $r \in \{1,\dots,n\}$，并返回同样范围内的值。$c$ 的取值也应在同一范围内。Sharon 的挑战是在有限次数的查询内，找到 $c$ 和 $r$ 使得 $f^c(r) = c$。 你知道 Sharon 的观点是正确的，决定帮助她。 在第一个样例中，$n=6$，隐藏函数为 $f(1)=4$，$f(2)=3$，$f(3)=5$，$f(4)=2$，$f(5)=4$，$f(6)=6$。在第二个样例中，$n=4$，$f(1)=2$，$f(2)=4$，$f(3)=2$，$f(4)=2$。

本题为交互题。你的程序将与交互器进行交互，交互器会读取你的标准输出，并向你的标准输入写入数据。交互过程如下： 交互器首先输出一行一个整数 $n$（$1 \leq n \leq 2\cdot 10^5$），表示隐藏函数 $f$ 的定义域为 $\{1,\dots,n\}$。 然后，你的程序最多可以进行 $1000$ 次查询以找到答案。每次查询通过输出一行形如 $\texttt{? c r}$（$1 \leq c, r \leq n$）实现。 交互器会回复一个整数 $h$（$1 \leq h \leq n$），即 $f^c(r)$ 的值。 当你确定存在某组 $c$ 和 $r$ 满足 $f^c(r) = c$ 时，输出一行 $\texttt{! c r}$（$1 \leq c, r \leq n$），交互随即结束。 输出答案不计入查询次数。 如果存在多组合法解，你可以输出任意一组。 交互器是非自适应的：隐藏函数 $f$ 在开始时已确定，不会根据你的查询改变。 每次输出后请务必刷新输出缓冲区。 题目提供了测试工具，方便你开发调试。 如果查询次数超过 $1000$，将判为错误答案。

（交互题，无需填写输出格式。）

由 ChatGPT 4.1 翻译