题意
已知kkk, aaa, ppp. 求 xk≡a (mod p)x^k\equiv a\ (mod\ p)xk≡a (mod p) 的所有根. 根的范围[0,p−1][0,p-1][0,p−1]. ppp为质数
分析
因为ppp是质数,那么一定有原根.设为ggg.
原根的性质如下:
- 对于[1,p−1][1,p-1][1,p−1]的所有iii,一定存在x∈[1,p−1]x\in[1,p-1]x∈[1,p−1]使得gx≡i (mod p)g^x\equiv i\ (mod\ p)gx≡i (mod p). 此时设xxx为I(i)I(i)I(i).
1.1.1.那么当aaa等于000
- 只有一个根就是000
2.2.2.当a∈[1,p−1]a\in[1,p-1]a∈[1,p−1]
- 画画柿子xk≡a (mod p)(gI(x))k≡a (mod p)(gk)I(x)≡a (mod p)\begin{aligned}x^k&\equiv a\ (mod\ p)\\(g^{I(x)})^k&\equiv a\ (mod\ p)\\(g^{k})^{I(x)}&\equiv a\ (mod\ p)\end{aligned}xk(gI(x))k(gk)I(x)≡a (mod p)≡a (mod p)≡a (mod p)
我们知道gkg^kgk,知道aaa,知道ppp.直接BSGSBSGSBSGS就行了.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int g, prime[100], cnt;
inline int qpow(int a, int b, int c) {
int re = 1;
while(b) {
if(b&1) re = 1ll * re * a % c;
a = 1ll * a * a % c; b >>= 1;
}
return re;
}
inline void Factor(int N) {
int tmp = N;
for(int i = 2; i*i <= N; ++i)
if(tmp % i == 0) {
prime[++cnt] = i;
while(tmp % i == 0) tmp /= i;
}
if(tmp > 1) prime[++cnt] = tmp;
}
inline int Get_g(int p) { //找原根
Factor(p-1);
for(int g = 2; ; ++g) {
bool flg = true;
for(int i = 1; i <= cnt; ++i)
if(qpow(g, (p-1)/prime[i], p) == 1)
{ flg = 0; break; }
if(flg) return g;
}
}
map<int, int>myhash;
vector<int>ans;
inline void Baby_Step_Giant_Step(int a, int b, int p) {
if(b == 1) ans.push_back(0);
myhash.clear();
int m = int(sqrt(p) + 1);
LL base = b;
for(int i = 0; i < m; ++i) {
myhash[base] = i;
base = 1ll * base * a % p;
}
base = qpow(a, m, p);
LL tmp = 1;
for(int i = 1; i <= m+1; ++i) {
tmp = 1ll * tmp * base % p;
if(myhash.count(tmp))
ans.push_back(i*m - myhash[tmp]);
}
}
int main() {
int p, k, a, g;
scanf("%d%d%d", &p, &k, &a);
if(!a) return puts("1"), puts("0"), 0;
//(g^I(x))^k = a (mod p)
//(g^k)^I(x) = a
Baby_Step_Giant_Step(qpow(g = Get_g(p), k, p), a, p);
for(int i = 0, siz = ans.size(); i < siz; ++i)
ans[i] = qpow(g, ans[i], p);
sort(ans.begin(), ans.end());
int siz = ans.size();
siz = unique(ans.begin(), ans.end()) - ans.begin();
printf("%d\n", siz);
for(int i = 0; i < siz; ++i)
printf("%d\n", ans[i]);
}