#P1319. Sgu261Discrete Roots

    ID: 331 传统题 1000ms 512MiB 尝试: 784 已通过: 203 难度: 7 上传者: 标签>CF2200提高+/省选-原根BSGS线性同余方程扩展欧几里得算法试除法分解质因数快速幂哈希表随机采样费马小定理

Sgu261Discrete Roots

题目描述

给出三个整数 p,k,ap,k,a,其中 pp 为质数,求出所有满足xk=a( mod  p),0≤x≤p−1x^k=a (\bmod\ p),0\leq x\leq p-1 的 xx。

输入格式

三个整数 p,k,ap,k,a。

输出格式

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

11 3 8
1
2

提示

2≤p≤1092\leq p\leq 10^9 2≤k≤105,0≤a<p2\leq k\leq 10^5,0\leq a<p。