#P6091. 【模板】原根

【模板】原根

题目描述

给定整数 nn,求它的所有原根。

为了减小你的输出量,给出输出参数 dd,设 nn 的所有原根有 cc 个,从小到大分别为 g1,,gcg_1,\ldots,g_c,你只需要依次输出 $g_d,g_{2d},\ldots,g_{\lfloor\frac{c}{d}\rfloor\times d}$。


如果你不了解原根的定义,可以自行查找资料或阅读下列定义:

正整数 gg 是正整数 nn 的原根,当且仅当 1gn11\leq g\leq n-1,且 ggnn 的阶为 φ(n)\varphi(n)

输入格式

本题包含多组数据

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

接下来 TT 行:每行两个整数 n,dn,d,表示一组询问数据。

输出格式

对于每组数据:

第一行输出一个整数 cc,表示 nn 的原根个数,第二行输出 cd\lfloor\dfrac{c}{d}\rfloor 个数,按照题目描述中要求输出。

注意:即使 cd=0\lfloor\dfrac{c}{d}\rfloor=0,也需要输出一个空行。

6
2 1
4 1
25 2
36 1
9 6
18 1
1
1 
1
3 
8
3 12 17 23 
0

2

2
5 11 

提示

【样例解释】

对于第 1,2,4,61,2,4,6 组数据,给出的 nn 的所有原根都出现在输出中。

对于第 33 组数据,2525 的原根集合为 {2,3,8,12,13,17,22,23}\{2,3,8,12,13,17,22,23\}

对于第 55 组数据,99 的原根集合为 {2,5}\{2,5\}

【数据范围】

对于 100%100\% 的数据,1T101\leq T\leq 102n1062\leq n\leq 10^61d2001\leq d\leq 200,保证输出的数的总个数不超过 10510^5