#P1420. Discrete Root

    ID: 432 传统题 1000ms 512MiB 尝试: 293 已通过: 133 难度: 7 上传者: 标签>CF2200提高+/省选-原根BSGS线性同余方程扩展欧几里得算法试除法分解质因数快速幂模逆元哈希表

Discrete Root

题目描述

已知 k,a,pk,a,p,求 xk≡a(modp)x^{k}\equiv a\pmod p 的所有根(根的范围 [0,p−1][0,p-1])。

输入格式

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

输出格式

第一行一个整数,表示符合条件的 xx 的个数。

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

11 3 8
1
2

数据范围

100%100\% 的数据满足 2≤p≤109,2≤k≤105,0≤a<p2\le p\le10^{9},2\le k\le10^{5},0\le a<p。

本站数据版本约定

模数 pp 保证为质数。