「ZJOI2020」密码

题目描述

Bob 喜欢 Alice。

Alice 和 Bob 想要进行加密通信，于是他们自己设计了一套加密算法进行身份验证。你知道这个加密算法并不可靠，并截获了 Alice 和 Bob 之间的信息。现在你想要恢复出 Alice 的密钥。

Alice 和 Bob 约定了一个大质数 $p$ ，一个随机范围值 $\text{err}$ 和一个在 $0 \sim p-1$ 之间均匀随机生成的整数密钥 $x$ 。其中 $p$ 和 $\text{err}$ 的值是公开的，而 $x$ 的值只有 Alice 和 Bob 知道。

当 Bob 想要确认 Alice 的身份时：

Bob 生成 $m$ 个在 $0 \sim p-1$ 之间均匀随机生成的 $a_i$ 并发给 Alice
对于每个 $a_i$ ，Alice 会返回给 Bob $a_i x$ 模 $p$ 的值
为了防止窃听，Alice 会给结果加上一个在 $-\lceil \frac{\text{err}}{2} \rceil$ 到 $\lceil \frac{\text{err}}{2} \rceil$ 之间均匀随机生成的扰动

即，Alice 会返回给 Bob $m$ 组形如：

a_i x + b_i \equiv c_i \pmod{p}

的等式，其中：

$b_i$ 为一个不公开的在 $-\lceil \frac{\text{err}}{2} \rceil$ 到 $\lceil \frac{\text{err}}{2} \rceil$ 之间均匀随机生成的数
$a_i$ 为随机生成的数
$a_i, p, \text{err}, c_i$ 为公开的数

第一行输入一个整数 $T$ ，表示数据组数。

对于每组数据：

符号的含义和题面中相同。

输出 $T$ 行，对于每组测试数据，输出一个 $0$ 到 $p - 1$ 之间整数表示答案。数据保证有解并且解唯一。