SGU 同餘方程 x^K ≡ A (mod P)：原根 + 大步小步 + 擴展歐幾里得完整解法

解法框架

1. 求 P 的**原根** g（生成元）。
2. 用**大步小步算法 (BSGS)** 求離散對數 t 使 g^t ≡ A (mod P)。
3. 設 x = g^w，則 g^{wK} ≡ g^t ⇒ wK ≡ t (mod P-1)。
4. 解線性同餘方程 K·w ≡ t (mod P-1)，用**擴展歐幾里得**求所有解 w。
5. 對每個 w，x = g^w mod P 即為答案。

關鍵子算法

原根查找

分解 P-1 質因子，檢查候選 g 是否對所有質因子 q 滿足 g^{(P-1)/q} ≠ 1。

BSGS (Baby-Step Giant-Step)

m = ceil(√P)。預計算 g^{0..m-1} 存哈希表。巨步計算 A·g^{-jm} 查表。時間 O(√P)。

線性同餘方程

K·w ≡ t (mod M)，M=P-1。
d = gcd(K,M)，若 d∤t 無解。
否則約分：(K/d)·w ≡ t/d (mod M/d)，求逆元得一組解，再加 M/d 得所有 d 個解。

特殊情況

• A=0：唯一解 x=0。
• P=2：直接枚舉 x=0,1。

複雜度

分解 P-1 O(√P)，BSGS O(√P)，擴展歐幾里得 O(log P)。P≤1e9 ⇒ √P≤31623，極快。