#3316. 「ZJOI2020」密码

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

Bob 喜欢 Alice。

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

Alice 和 Bob 约定了一个大质数 p ,一个随机范围值 err 和一个在 0 \sim p−1 之间均匀随机生成的整数密钥 x 。其中 p 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 {err}2 \rceil \lceil \frac {err}2 \rceil 之间均匀随机生成的扰动。

即,Alice 会返回给 Bob m 组形如 a_i x + b_i \equiv c_i \pmod p 的等式,其中 b_i 为一个不公开的在 -\lceil \frac {err}2 \rceil \lceil \frac {err}2 \rceil 之间均匀随机生成的数, a_i 为随机生成的数, a_i,p,err,c_i 为公开的数。

你获得了 Alice 返回的这 m 组等式(即 m a_i c_i ),你需要求出 x 的值。

输入格式

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

对于每组数据,第一行输入三个整数 m, p, err 。接下来 m 行,每行两个整数 a_i, c_i 。符号的含义和题面中相同。

输出格式

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

样例

见附加文件中 password1.inpassword1.out。该样例满足题目中提到的所有随机生成的性质。

数据范围与提示

对于前 10\% 的数据,满足 err\le 10^6

对于前 20\% 的数据,满足 err\le 10^8

对于前 30\% 的数据,满足 err \le 10^{11}

对于前 40\% 的数据,满足 err \le 10^{12}

对于另外 20\% 的数据,满足 p \le 10^{16}, m = 2000

对于 100\% 的数据,满足 10^{15} \le p \le 10^{18}, 50 \le m \le 2000, 1 \le err \le 0.01p, 1 \le T \le 5, 0 \le a_i, c_i \le p − 1 ,保证 p 为素数。