이산 k 제곱근 (Discrete Kth Root) 은 소수 p 에 대해 x^k ≡ a (mod p) 를 만족하는 모든 x 를 찾는 문제. 원시근 (primitive root) 으로 지표화하여 이산 로그 문제로 환원한 뒤 BSGS 와 확장 유클리드 호제법으로 해결. O(√p log p + Ans·log p).
문제 상황과 동기
x^k ≡ a (mod p) 의 모든 해를 구하라. p 는 소수, k ≥ 2.
naive: x = 0..p-1 순회 + 거듭제곱. O(p log k). p=10^9 면 불가능.
원시근 + BSGS: O(√p log p) 로 하나의 해 탐색 + 모든 해 나열.
핵심 통찰: 군 (Z/pZ)^ 는 순환군. 원시근 g 로 모든 원소를 g^y 로 표현하면 x^k ≡ a 는 k·y ≡ ind_g(a) (mod φ(p)) 로 변환.*
시각화
핵심 아이디어
원시근 g 로 지표화하여 이산 로그 문제로 변환: g^(k·y) ≡ g^b → k·y ≡ b (mod p-1).
원시근 g 탐색 (위수 = p-1).
a 의 지표 b 를 BSGS 로: g^b ≡ a.
x = g^y → 선형 합동식 k·y ≡ b (mod p-1).
확장 유클리드로 모든 y 탐색. 각 y → x = g^y mod p.
모든 해는 x = g^{y_0 + i·Δ} 꼴, Δ = (p-1) / gcd(k, p-1).
k·y ≡ b (mod p-1) 의 해: d = gcd(k, p-1) if b % d != 0: 해 없음 k' = k/d, m' = (p-1)/d, b' = b/d y_0 = (b' · k'^{-1}) mod m' Δ = m' y_i = y_0 + i·Δ, i = 0..d-1
알고리즘
discrete_kth_root(p, k, a): if a == 0: return [0] g = find_primitive_root(p) b = bsgs(g, a, p) # g^b ≡ a d = gcd(k, p - 1) if b % d != 0: return [] m = (p - 1) / d k_inv = modular_inverse(k / d, m) y0 = (b / d) * k_inv % m solutions = [] for i = 0..d-1: y = y0 + i * m solutions.append(g^y % p) sort(solutions) return solutions
구현
// Discrete Kth Root: x^k = a (mod p)#include <bits/stdc++.h>using namespace std;using ll = long long;ll modpow(ll a, ll b, ll m) { ll r = 1; while (b) { if (b & 1) r = r * a % m; a = a * a % m; b >>= 1; } return r;}ll primitive_root(ll p) { vector<ll> pf; ll tmp = p - 1; for (ll i = 2; i * i <= tmp; i++) if (tmp % i == 0) { pf.push_back(i); while (tmp % i == 0) tmp /= i; } if (tmp > 1) pf.push_back(tmp); for (ll g = 2; g < p; g++) { bool ok = 1; for (ll f : pf) if (modpow(g, (p - 1) / f, p) == 1) { ok = 0; break; } if (ok) return g; } return -1;}ll bsgs(ll a, ll b, ll p) { if (b == 1) return 0; ll n = sqrt(p) + 1; unordered_map<ll, ll> baby; ll cur = 1; for (ll j = 0; j < n; j++) { if (!baby.count(cur)) baby[cur] = j; cur = cur * a % p; } ll factor = modpow(a, p - 1 - (n - 1), p); cur = b; for (ll i = 0; i < n; i++) { if (baby.count(cur)) return i * n + baby[cur]; cur = cur * factor % p; } return -1;}ll modinv(ll a, ll m) { return modpow(a, m - 1, m); }ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }int main() { ll p, k, a; cin >> p >> k >> a; if (a == 0) { cout << "1\n0"; return 0; } ll g = primitive_root(p), b = bsgs(g, a, p), d = gcd(k, p - 1); if (b % d != 0) { cout << "0"; return 0; } ll m = (p - 1) / d; ll y0 = (b / d) * modinv(k / d, m) % m; vector<ll> ans; for (ll i = 0; i < d; i++) ans.push_back(modpow(g, y0 + i * m, p)); sort(ans.begin(), ans.end()); cout << ans.size() << "\n"; for (ll x : ans) cout << x << " "; return 0;}
# Discrete Kth Root: x^k = a (mod p)import math, sysdef modpow(a, b, m): r = 1 while b: if b & 1: r = r * a % m a = a * a % m; b >>= 1 return rdef primitive_root(p): pf = [] tmp = p - 1 for i in range(2, int(tmp ** 0.5) + 1): if tmp % i == 0: pf.append(i) while tmp % i == 0: tmp //= i if tmp > 1: pf.append(tmp) for g in range(2, p): if all(modpow(g, (p - 1) // f, p) != 1 for f in pf): return g return -1def bsgs(a, b, p): if b == 1: return 0 n = int(math.isqrt(p)) + 1 baby = {} cur = 1 for j in range(n): if cur not in baby: baby[cur] = j cur = cur * a % p factor = pow(a, -n, p) cur = b for i in range(n): if cur in baby: return i * n + baby[cur] cur = cur * factor % p return -1p, k, a = map(int, sys.stdin.readline().split())if a == 0: print(f"1\n0") sys.exit()g = primitive_root(p)b = bsgs(g, a, p)d = math.gcd(k, p - 1) if hasattr(math, 'gcd') else __import__('math').gcd(k, p - 1)d = math.gcd(k, p - 1)if b % d != 0: print("0") sys.exit()m = (p - 1) // dy0 = (b // d) * pow(k // d, -1, m) % mans = sorted(modpow(g, y0 + i * m, p) for i in range(d))print(len(ans))print(*ans)
💬 댓글