#P6634. [ZJOI2020] 密码

[ZJOI2020] 密码

题目描述

Bob 喜欢 Alice。

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

Alice 和 Bob 约定了一个大质数 pp,一个随机范围值 errerr 和一个在 0p10 \sim p - 1 之间均匀随机生成的整数密钥 xx。其中 pperrerr 的值是公开的,而 xx 的值只有 Alice 和 Bob 知道。

当 Bob 想要确认 Alice 的身份时,Bob 会生成 mm 个在 0p10\sim p-1 之间均匀随机生成的 aia_i 并发给 Alice。对于每个 aia_i,Alice 会返回给Bob aixa_i xpp 的值。为了防止窃听,Alice 会给结果加上一个在 err2-\lceil \frac {err}2 \rceilerr2\lceil \frac {err}2 \rceil 之间均匀随机生成的扰动。

即,Alice 会返回给 Bob mm 组形如 aix+bici(modp)a_i x + b_i \equiv c_i \pmod p 的等式,其中 bib_i 为一个不公开的在 err2-\lceil \frac {err}2 \rceilerr2\lceil \frac {err}2 \rceil 之间均匀随机生成的数,aia_i 为随机生成的数,ai,p,err,cia_i,p,err,c_i 为公开的数。

你获得了 Alice 返回的这 mm 组等式(即 mmaia_icic_i),你需要求出 xx 的值。

输入格式

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

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

输出格式

输出 TT 行,
对于每组测试数据,输出一个 00p1p - 1 之间整数表示答案。数据保证有解并且解唯一。

见下发文件。该样例满足题目中提到的所有随机生成的性质。


提示

对于前 10%10\% 的数据,满足 err106err \le 10^6
对于前 20%20\% 的数据,满足 err108err \le 10^8
对于前 30%30\% 的数据,满足 err1011err \le 10^{11}
对于前 40%40\% 的数据,满足 err1012err \le 10^{12}
对于另外 20%20\% 的数据,满足 p1016p \le 10^{16}m=2000m = 2000
对于 100%100\% 的数据,满足 1015p101810^{15} \le p \le 10^{18}50m200050 \le m \le 20001err0.01p1 \le err \le 0.01p1T51 \le T \le 50ai,cip10 \le a_i,c_i \le p-1,保证 pp 为素数。