随机数生成器

jijidawang · 2024-09-08 21:00:39 · 题解

t=1

输出 \frac{s^{x+1}}{s^x}。

t=2

枚举 x，询问能问出来一段 (x+i)^s\equiv a_i\pmod p。

取 p 的原根 g，令 \operatorname{ind}_g(x) 是 x 对 g 的指标。限制即为 s\operatorname{ind}_g(x+i)\equiv\operatorname{ind}(a_i)\pmod{p-1}。

注意到相当于解线性同余方程组，分别解出每个方程后 exCRT 合并即可。