『STA - R8』随机数生成器
题目背景
**Upd on 2024/10/22** 加入一组 Hack 数据(#13)
题目描述
**这是一道交互题。**
Lloyd 有一个随机数生成器,对于随机种子 $s$ 和生成器类型 $t$,它第 $x$ 次($x<p$)生成的随机数是:
$$r_{s,t}(x)=\begin{cases}s^x\bmod p&t=1\\x^s\bmod p&t=2\end{cases}$$
其中 $p$ 是一个固定素数。$0\le s<p-1$。
现在给定 $p,t$。已知随机数生成器在你询问之前已经生成过若干随机数,而在你生成随机数的时候不会有任何其他随机数生成访问(也就是你生成的是一段连续的随机数)。你每次可以调用随机数生成器来获取一个随机数,并且在若干次调用之后找出随机数种子 $s$ 的值。**保证有解且 5 次询问后一定能得到唯一的解。**
***
**实现细节**
本题采用 IO 交互模式。
第一行输入两个正整数 $t,p$。
接下来,可以向交互库发送以下两种操作:
- `?`,表示调用一次随机数生成器,随即你可以从标准输入中读入随机数生成器生成的数值。
- `! s`,报告你发现的 $s$。
发送 `!` 操作后你应该立即结束程序。另外在每一次操作后都需要清空缓冲区。评分方式见数据范围部分。
如果你的操作不符合交互格式可能出现不可预料的结果。保证在交互次数不超过 19930(也就是至少可以获得 1 分)时交互库的运行时间不超过 100ms。对于 19930 之上的交互次数不保证交互库运行时间。
输入输出格式
输入格式
见题目描述中实现细节部分。
输出格式
见题目描述中实现细节部分。
输入输出样例
输入样例 #1
1 10007
4960
输出样例 #1
?
! 114
输入样例 #2
2 10007
4960
6980
输出样例 #2
?
?
! 514
说明
**样例解释**
样例仅供参考,不一定具有实际逻辑。
第一组样例:$p=10007$,$s=114$,在询问之前生成过 $513$ 次随机数。
第二组样例:$p=10007$,$s=514$,在询问之前生成过 $113$ 次随机数。
***
**数据范围**
**本题采用捆绑测试。**(Subtask 分数为 Subtask 内各测试点分数之最小值)
- Subtask 1 (20pts):$t=1$。
- Subtask 2 (20pts):$p\le 10^3$。
- Subtask 3 (60pts):无特殊限制。
对于全部数据,$2\le p\le2\times10^6$ 且 $p$ 是素数,$t\in\{1,2\}$,保证有解。
对于每个测试点,如果你向交互库发送了 $c$ 次 `?` 操作,那么你可以得到的分数由如下表达式给出:
$$\mathrm{score}=\begin{cases}100&c\le 5\\\max\{0,100-\lceil10\ln(c)\rceil\}&\text{otherwise.}\end{cases}$$