Description

Heidi 正在分析一个特殊的设备。该设备以一个 $a$ 作为输入，并使用以下伪代码和存储在设备中的一些整数 $d$ 和 $n$ 计算 $a^d \bmod n$：

modPow(a, d, n) {
  r = 1;
  for (i = 0; i < 60; ++i) {
    if ((d & (1 << i)) != 0) {
      r = r * a % n;
    }
  a = a * a % n;
  }
}

注意，伪代码假设整数可以是任意大小，$<<$ 表示按位左移，& 表示按位与，% 表示取模。

设备不会告诉 Heidi 计算结果。然而，Heidi 可以测量计算所需的时间。她知道只有模 $n$ 的乘法（上述伪代码中的第 5 行和第 7 行）需要可测量的时间，其他所有行可以假设为 0 纳秒。

此外，她知道将 $x$ 和 $y$ 模 $n$ 相乘需要 $(\text{bits}(x) + 1) \cdot (\text{bits}(y) + 1)$ 纳秒，其中 $\text{bits}(x)$ 是 $x$ 的二进制表示中不含前导零的位数，更正式地，$\text{bits}(x) = \lceil \log_2 (x + 1) \rceil$。

Heidi 知道整数 $n$，但不知道整数 $d$。她想通过将不同的整数 $a$ 作为输入提供给设备，并测量每个 $a$ 的计算时间来找到 $d$。

她知道 $n$ 和 $d$ 是通过以下方式选择的：首先，两个具有 30 位二进制表示的素数 $p$ 和 $q$（换句话说，在 $2^{29}$ 和 $2^{30} - 1$ 之间）被独立且均匀地随机选择。然后计算 $n = p \cdot q$。然后计算 $m = \varphi(n) = (p-1) \cdot (q-1)$。然后在 $1$ 到 $m - 1$ 之间均匀随机选择 $d$，使其与 $m$ 互质。

交互协议

首先，测试系统写入整数 $n$——设备使用的模数。注意，$n$ 和隐藏的数字 $d$ 保证是按照上述过程生成的。

你的解决方案应打印两种类型的请求：

• “? a” 告诉设备以 $a$ 作为输入。$a$ 必须是 $0$ 到 $n-1$ 之间的整数。测试系统会返回设备计算 modPow(a , d , n) 所需的时间（以纳秒为单位）。

• “! d” 告诉你的程序已确定的 $d$ 值。

不要忘记在每次请求后刷新输出！

你的解决方案必须发出恰好一个第二种类型的请求，该请求必须是最后一个请求，并且解决方案在发出该请求后必须正常终止。

你的解决方案最多可以发出 $30,000$ 个第一种类型的请求。

你的解决方案将在 $30$ 个测试用例上运行，每次运行处理一个 $(n , d)$ 对。对于每个测试用例，数字 $n$ 和 $d$ 是固定的，并且是使用上述过程生成的。下面的例子不是以这种方式生成的，因此不会用于测试你的解决方案；它仅用于说明输入/输出格式并为计算时间的合理性检查提供一个 sanity check。

15
980
293

? 3
? 8
! 5

Hint

题面翻译由 ChatGPT-4o 提供。