1. Abridged Problem Statement
Given a prime P, integers K and A (0≤A<P), find all integers x in [0..P−1] satisfying
 x^K ≡ A  (mod P).
Output the number of solutions and the solutions in ascending order.

2. Detailed Editorial

Overview
We need to solve the congruence x^K ≡ A mod P, where P is prime. If A=0 the only root is x=0. Otherwise, we reduce the problem to a discrete logarithm and a linear congruence.

Steps

1. Handle A=0.
   If A=0, then x^K ≡ 0 mod P ⇒ x≡0 is the only root. Return {0}.

2. Check solvability via Fermat’s little theorem.
   For a solution to exist, A^((P−1)/d) ≡1 mod P, where d=gcd(K,P−1). If this fails, there are no solutions.

3. Compute a primitive root g of P.
   - Factor φ(P)=P−1 into its distinct prime factors.
   - Test candidates g=2,3,... until for every prime factor q of P−1 we have g^{(P−1)/q}≠1 mod P.

4. Compute the discrete logarithm T such that g^T ≡ A mod P (baby-step giant-step).
   Let m=⌈√(P−1)⌉. Precompute baby steps g^j for 0≤j<m into a hash map. Then compute giant steps A·(g^{−m})^i for i=0.. until a match. Recover T=i·m + j.

5. Solve the linear congruence K·y ≡ T  (mod P−1).
   - Let d=gcd(K,P−1).
   - If d ∤ T, no solution.
   - Otherwise set K'=K/d, M=(P−1)/d, T'=T/d.
   - Compute inv_K' = inverse of K' mod M (extended gcd).
   - A particular solution is y0 = T'·inv_K' mod M.
   - All solutions are y = y0 + i·M for i=0..d−1.

6. Convert solutions y back to x:
   x_i = g^{y_i} mod P. Sort and deduplicate.

Complexities
– Finding primitive root: O(sqrt(P−1)/log + factor count) but P−1≤1e9 so factoring in O(√P) worst-case.
– Discrete log: O(√P log P). For P up to 1e9 this is ~3·10^4 steps, acceptable.
– Overall fits in 1s with optimized code.

3. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t p, k, a;

void read() { cin >> p >> k >> a; }

int64_t mul_mod(int64_t x, int64_t y, int64_t mod) {
    return (int64_t)((__int128)x * y % mod);
}

int64_t ext_gcd(int64_t a, int64_t b, int64_t& x, int64_t& y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int64_t x1, y1;
    int64_t g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int64_t inv_mod(int64_t a, int64_t m) {
    int64_t x, y;
    int64_t g = ext_gcd(((a % m) + m) % m, m, x, y);
    if(g != 1) {
        return -1;
    }
    return ((x % m) + m) % m;
}

int64_t mod_exp(int64_t base, int64_t exp, int64_t mod) {
    int64_t result = 1;
    base %= mod;
    if(base < 0) {
        base += mod;
    }

    while(exp > 0) {
        if(exp & 1) {
            result = mul_mod(result, base, mod);
        }
        base = mul_mod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

vector<int64_t> factorize(int64_t n) {
    vector<int64_t> factors;
    for(int64_t i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            factors.push_back(i);
            while(n % i == 0) {
                n /= i;
            }
        }
    }
    if(n > 1) {
        factors.push_back(n);
    }
    return factors;
}

int64_t find_primitive_root(int64_t mod) {
    if(mod == 2) {
        return 1;
    }

    int64_t phi = mod - 1;
    vector<int64_t> prime_factors = factorize(phi);
    for(int64_t g = 2; g < 200000; g++) {
        bool ok = true;
        for(int64_t f: prime_factors) {
            if(mod_exp(g, phi / f, mod) == 1) {
                ok = false;
                break;
            }
        }
        if(ok) {
            return g;
        }
    }
    return -1;
}

int64_t baby_step_giant_step(int64_t base, int64_t target, int64_t mod) {
    if(target % mod == 1) {
        return 0;
    }

    base %= mod;
    target %= mod;

    int64_t m = (int64_t)sqrtl((long double)(mod - 1)) + 2;

    unordered_map<int64_t, int64_t> baby;
    int64_t cur = 1;
    for(int64_t j = 0; j < m; j++) {
        if(!baby.count(cur)) {
            baby[cur] = j;
        }
        cur = mul_mod(cur, base, mod);
    }

    int64_t a_inv_m = mod_exp(base, (mod - 1) - m, mod);

    int64_t giant = target;
    for(int64_t i = 0; i < m; i++) {
        auto it = baby.find(giant);
        if(it != baby.end()) {
            return i * m + it->second;
        }
        giant = mul_mod(giant, a_inv_m, mod);
    }
    return -1;
}

void solve() {
    // Solve x^K = A (mod P) for prime P.
    //
    // - If A == 0 the only root is 0.
    //
    // - Let d = gcd(K, P-1). A solution exists iff A^((P-1)/d) == 1 (mod P).
    //
    // - Take a primitive root alpha of P (found by checking candidates against
    //   the prime factors of P-1). Solve the discrete log T with alpha^T == A
    //   via baby-step giant-step, so x = alpha^L means we need K*L == T
    //   (mod P-1).
    //
    // - That linear congruence is solvable iff d | T. Reduce to K'*L == T'
    //   (mod M) with T'=T/d, M=(P-1)/d, K'=K/d, giving L0 = T'*inv(K') (mod M).
    //   The d distinct roots are alpha^(L0 + i*M) for i in [0, d), which we
    //   sort and deduplicate.

    if(a == 0) {
        cout << 1 << "\n";
        cout << 0 << "\n";
        return;
    }

    int64_t gx, gy;
    int64_t d = ext_gcd(k, p - 1, gx, gy);
    if(mod_exp(a, (p - 1) / d, p) != 1) {
        cout << 0 << "\n";
        return;
    }

    int64_t alpha = find_primitive_root(p);
    if(alpha == -1) {
        cout << 0 << "\n";
        return;
    }

    int64_t t = baby_step_giant_step(alpha, a, p);
    if(t == -1 || t % d != 0) {
        cout << 0 << "\n";
        return;
    }

    int64_t t_prime = t / d;
    int64_t m = (p - 1) / d;
    int64_t k_prime = ((k / d) % m + m) % m;

    int64_t inv_k_prime = (m == 1) ? 0 : inv_mod(k_prime, m);
    if(inv_k_prime == -1) {
        cout << 0 << "\n";
        return;
    }

    int64_t l0 = (m == 1) ? 0 : mul_mod(t_prime % m, inv_k_prime, m);

    set<int64_t> roots;
    for(int64_t i = 0; i < d; i++) {
        int64_t exponent = (l0 + i * m) % (p - 1);
        roots.insert(mod_exp(alpha, exponent, p));
    }

    cout << roots.size() << "\n";
    bool first = true;
    for(int64_t x: roots) {
        if(!first) {
            cout << ' ';
        }
        cout << x;
        first = false;
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python Solution
```python
import sys
from math import gcd, isqrt

def mod_exp(base, exp, mod):
    # Fast power: compute (base^exp) % mod in O(log exp).
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return result

def extended_gcd(a, b):
    # Returns (g, x, y) so that a*x + b*y = g = gcd(a, b).
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = extended_gcd(b, a % b)
    # Back-substitute
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)

def inv_mod(a, m):
    # Modular inverse of a mod m, if it exists.
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        return None
    return x % m

def factorize(n):
    # Return distinct prime factors of n in O(sqrt(n)).
    factors = []
    limit = isqrt(n) + 1
    for i in range(2, limit):
        if n % i == 0:
            factors.append(i)
            while n % i == 0:
                n //= i
    if n > 1:
        factors.append(n)
    return factors

def find_primitive_root(p):
    # Finds smallest generator g of Z_p^*.
    if p == 2:
        return 1
    phi = p - 1
    primes = factorize(phi)
    # A candidate g is primitive iff for every prime factor q,
    # g^(phi/q) != 1 mod p.
    for g in range(2, p):
        ok = True
        for q in primes:
            if mod_exp(g, phi // q, p) == 1:
                ok = False
                break
        if ok:
            return g
    return None

def baby_step_giant_step(a, b, p):
    # Solve a^x ≡ b mod p, return x or None.
    a %= p; b %= p
    if b == 1:
        return 0
    m = isqrt(p - 1) + 1
    # Baby steps: store a^j
    baby = {}
    cur = 1
    for j in range(m):
        if cur not in baby:
            baby[cur] = j
        cur = cur * a % p
    # Compute a^{-m} = a^(p-1-m) mod p
    a_inv_m = mod_exp(a, p - 1 - m, p)
    giant = b
    for i in range(m):
        if giant in baby:
            return i * m + baby[giant]
        giant = giant * a_inv_m % p
    return None

def solve_kth_roots(P, K, A):
    # Special case A = 0
    if A == 0:
        return 1, [0]
    # d = gcd(K, P-1)
    d = gcd(K, P - 1)
    # Check if A^((P-1)/d) ≡ 1 mod P; otherwise no roots.
    if mod_exp(A, (P - 1) // d, P) != 1:
        return 0, []
    # Find primitive root and discrete log T: g^T ≡ A
    g = find_primitive_root(P)
    T = baby_step_giant_step(g, A, P)
    if T is None or T % d != 0:
        return 0, []
    # Solve K*y ≡ T (mod P-1)
    Kp = K // d
    Mp = (P - 1) // d
    Tp = T // d
    invKp = inv_mod(Kp, Mp)
    y0 = Tp * invKp % Mp
    # Generate all d solutions y = y0 + i*Mp
    roots = []
    for i in range(d):
        exp = (y0 + i * Mp) % (P - 1)
        roots.append(mod_exp(g, exp, P))
    roots = sorted(set(roots))
    return len(roots), roots

def main():
    data = sys.stdin.read().split()
    P, K, A = map(int, data)
    cnt, ans = solve_kth_roots(P, K, A)
    print(cnt)
    if cnt > 0:
        print(*ans)

if __name__ == "__main__":
    main()
```

5. Compressed Editorial
1) If A=0, the only solution is x=0.
2) Let d=gcd(K,P−1). Require A^{(P−1)/d}≡1 or no roots.
3) Find primitive root g mod P.
4) Compute T=discrete_log_g(A).
5) Solve K·y≡T (mod P−1): d divides T, let y0 = (T/d)·(K/d)^{-1} mod ((P−1)/d).
6) Solutions y=y0+i·((P−1)/d), i=0..d−1 ⇒ x=g^y mod P. Sort and output.
