题目描述

给出三个整数p,k,a,其中p为质数，求出所有满足x^k=a (mod p),0<=x<=p-1的x。

输入

三个整数p,k,a。

输出

第一行一个整数，表示符合条件的x的个数。 第二行开始每行一个数，表示符合条件的x,按从小到大的顺序输出。

样例输入

11 3 8

样例输出

1

2

提示

2<=p<p<=10^9

 2<=k<=100000,0<=a

 

首先求出$p$的原根$g$，再求出$a$的指标$b$，即$g^b\equiv a(mod\ p)$。我们知道对于$[0,p-1]$中任意数都能用原根的幂次表示，所以将$x$表示成$g^y$即$g^y\equiv x(mod\ p)$，那么原式就变成了$(g^y)^k\equiv g^b(mod\ p)->g^{yk}\equiv g^b(mod\ p)$。根据欧拉定理可知$g^{p-1}\equiv 1(mod\ p)$，所以$yk\equiv b(mod\ (p-1))$，只需要用$exgcd$求出$[0,p-1]$内所有的$y$即可。

#include
      
       #include