UVA 1426 Discrete Square Roots - 已知一解求模平方根所有解

題目大意

給定 X, N, R，已知 R² ≡ X (mod N)。
求所有 1 ≤ r < N 滿足 r² ≡ X (mod N)。

數學轉換

設另一解為 r₁。則：

R² ≡ X (mod N)
r₁² ≡ X (mod N)
相減：R² - r₁² ≡ 0 (mod N)
(R - r₁)(R + r₁) ≡ 0 (mod N)

解法：枚舉因式分解

令 A = R + r₁, B = R - r₁。則 A × B ≡ 0 (mod N)。
枚舉 N 的因數對 (d, N/d)，設：

• A = d × k_a
• B = (N/d) × k_b

則 d·k_a - (N/d)·k_b = 2R。
這是關於 k_a, k_b 的線性不定方程，可用擴展歐幾里得求通解，進而得到 r₁。

程式碼核心

set ans;
ll exgcd(ll a, ll b, ll &x, ll &y) { ... }

void mod_linear(ll a, ll b, ll n) {
    // 解 a*x ≡ b (mod n)
    ll x, y, d = exgcd(a, n, x, y);
    if (b % d) return;
    x = x * (b/d) % (n/d);
    if (x < 0) x += n/d;
    ll step = n / d;
    for (ll t = x; t < N; t += step) {
        ll r1 = (a*t - b/2) % N; // 還原 r1
        if (r1 < 0) r1 += N;
        ans.insert(r1);
    }
}

int main() {
    while (scanf("%lld%lld%lld", &X, &N, &R) == 3 && N) {
        ans.clear();
        for (ll d = 1; d*d <= N; d++) if (N % d == 0) {
            mod_linear(d, 2*R, N/d);
            if (d*d != N) mod_linear(N/d, 2*R, d);
        }
        printf("Case %d:", ++cas);
        for (ll v : ans) printf(" %lld", v);
        puts("");
    }
}

複雜度

• 枚舉因數 O(√N)
• 每個因數解線性同餘 O(log N)
• 總計 O(√N log N)

關鍵點

• 用 set 自動去重並排序
• 處理 d 和 N/d 兩種因式分解
• 通解步長為 n/d，遍歷範圍 [0, N)