#P18664. Classic: Classical Problem

    ID: 18000 传统题 5000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-二分答案原根卷积转化NTT试除法分解质因数快速幂

Classic: Classical Problem

Classic: Classical Problem

“似曾相识!我以前刚来过这里。”——Dave Rodgers,Deja Vu

这是一个经典问题,我们就简短一些吧。

给定一个含有 nn 个数的集合 SS,以及一个素数 pp。对于整数 cc,定义

Sc={(c⋅x) mod p∣x∈S}.S_c=\{(c\cdot x)\bmod p\mid x\in S\}.

集合的 mex⁡\operatorname{mex} 是没有出现在集合中的最小非负整数。

请找出所有满足 0≤c<p0\le c<p、使得 mex⁡(Sc)\operatorname{mex}(S_c) 最大的整数 cc。

输入格式

输入包含多组测试数据。第一行包含整数 TT,表示测试数据的组数。

对于每组数据:

  • 第一行包含两个整数 n,pn,p,满足 1≤n≤p≤2×1051\le n\le p\le2\times10^5。保证 pp 是素数。
  • 第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,表示集合 SS 中的元素,满足 0≤ai<p0\le a_i<p。保证任意两个元素互不相同,即 i≠ji\ne j 时 ai≠aja_i\ne a_j。

保证所有测试数据的 pp 之和不超过 2×1052\times10^5。

输出格式

对于每组数据,第一行输出两个整数 k,mk,m,分别表示最优乘数 cc 的数量,以及最大的 mex⁡(Sc)\operatorname{mex}(S_c)。

第二行输出 kk 个整数,按严格递增顺序列出所有最优的 cc。需要输出全部最优乘数。

样例输入 1

3
2 3
0 2
3 5
2 3 4
3 5
0 2 3

样例输出 1

1 2
2
1 1
0
2 2
2 3