#C2023C. 挑战量子密码学

挑战量子密码学

本题并不难。如果你不会实现量子计算机,可以回过头看看2022年新生赛的B题

题目背景

旧时代的NP\text{NP}毫无意义,我们The First Island of Solitude的量子计算机时代之树将遥遥领先。

题目描述

阿比盖尔在紫色深渊花园发现了一个古老的人类密码系统,这个系统有nn组密码,第ii组密码有kik_i均为质数的密钥p1,p2,,pkip_1,p_2,\dots,p_{k_i},一个公开信息Ni=j=1kipjN_i=\prod_{j=1}^{k_i}p_j和一个加密信息Mi=i=1kipjM_i=\sum_{i=1}^{k_i}p_j

由于历史的变迁,密码系统已经破损不堪,每一组密码仅剩下两个密钥还未被揭露。然而众所周知,在非量子领域,整数分解问题是一个NPco-NP\text{NP}\cup\text{co-NP}问题,因此剩下的两个密钥仍然无法在非常快速的时间内破解。但是,阿比盖尔拥有的时代之树的力量——也就是你——破解这个问题是非常简单的,现在你需要证明自己能够解决这个问题。

阿比盖尔希望你能一次性解决羸弱的人类无法破解的密钥,因此她希望问题强制在线;关于“强制在线”的详细解释请参考“输入格式”。

输入格式

输入第一行包含一个整数nn,表示密码的组数。

接下来nn行,第ii行的第一个整数表示kik_i,第二个整数表示NiN_i,接下来的ki2k_i-2个整数表示已经被揭露的密钥。“强制在线”的含义是,这些数字都是被加密的,你需要将这些输入的数字全部按位异或上一组密码的Mi1M_{i-1} 来得到真实的数字。特别地,定义M0=0M_0=0

输出格式

输出共nn行,第ii行包含两个整数,表示第ii组密码未被揭露的两个密钥,按从小到大的顺序输出。你的答案与正确答案的相对误差或绝对误差不超过101110^{-11}

也就是说,如果你给出的答案是aa,正确答案是bb,你的答案被认为是正确的当且仅当abmax(1,b)<1011\frac {|a-b|}{\max{(1,b)}}<10^{-11}

样例

2
2 21
14 216 8 9
3 7
5 7

数据范围

对于20%20\%的数据,n1n\le 1

对于100%100\%的数据,1n1001\le n\le 100

对于第ii组密码,2ki10,4Ni<26402\le k_i\le 10,4\le N_i<2^{640},每一个密钥的大小均不超过2ni+42^{n-i+4}

提示

由于本题中的整数较大,可能需要使用Python或类似的语言完成解题。

axx=aa\oplus x\oplus x=a.