给定\(p, k, A\)，满足\(k, p\)是质数，求
\[x^k \equiv A \mod p\]
不会。。。
upd:3:29
两边取指标，是求
\[k\text{ind}_x\equiv \text{ind}_A\mod p-1\]
的解数，先求最小的解，然后暴力求之后的就行了。
#include <iostream>
#include <map>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
typedef long long LL; vector<LL> f, as;
LL fast_pow(LL base, LL index, LL mod) {
LL ret = ;
for(; index; index >>= , base = base * base % mod)
if(index & ) ret = ret * base % mod;
return ret;
}
bool test_Primitive_Root(LL g, LL p) {
for(LL i = ; i < f.size(); ++i)
if(fast_pow(g, (p - ) / f[i], p) == )
return ;
return ;
}
LL get_Primitive_Root(LL p) {
f.clear();
LL tmp = p - ;
for(LL i = ; i <= tmp / i; ++i)
if(tmp % i == )
for(f.push_back(i); tmp % i == ; tmp /= i);
if(tmp != ) f.push_back(tmp);
for(LL g = ; ; ++g) {
if(test_Primitive_Root(g, p))
return g;
}
}
LL get_Discrete_Logarithm(LL x, LL n, LL m) {
map<LL, int> rec;
LL s = (LL)(sqrt((double)m) + 0.5), cur = ;
for(LL i = ; i < s; rec[cur] = i, cur = cur * x % m, ++i);
LL mul = cur;
cur = ;
for(LL i = ; i < s; ++i) {
LL more = n * fast_pow(cur, m - , m) % m;
if(rec.count(more))
return i * s + rec[more];
cur = cur * mul % m;
}
return -;
}
LL ext_Euclid(LL a, LL b, LL &x, LL &y) {
if(b == ) {
x = , y = ;
return a;
} else {
LL ret = ext_Euclid(b, a % b, y, x);
y -= x * (a / b);
return ret;
}
}
void solve_Linear_Mod_Equation(LL a, LL b, LL n) {
LL x, y, d;
as.clear();
d = ext_Euclid(a, n, x, y);
if(b % d == ) {
x %= n, x += n, x %= n;
as.push_back(x * (b / d) % (n / d));
for(LL i = ; i < d; ++i)
as.push_back((as[] + i * n / d) % n);
}
} int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);
#endif LL p, k, a;
cin >> p >> k >> a;
if(a == ) {
puts("1\n0");
return ;
}
LL g = get_Primitive_Root(p);
LL q = get_Discrete_Logarithm(g, a, p);
solve_Linear_Mod_Equation(k, q, p - );
for(int i = ; i < as.size(); ++i)
as[i] = fast_pow(g, as[i], p);
sort(as.begin(), as.end());
printf("%d\n", as.size());
for(int i = ; i < as.size(); ++i) {
printf("%lld%c", as[i], i == as.size() - ? '\n' : ' ');
}
return ;
}