Quadratic equation - 题解

标签与难度

标签: 数论, 模运算, 二次剩余, Cipolla算法, Tonelli-Shanks算法, 费马小定理, 快速幂, 数学 难度: 2100

题目大意喵~

你好呀，master~ Amy小姐姐给B先生出了一道数学题，我们一起来帮帮他吧，喵~

题目是这样子的：给定两个整数 $b$ 和 $c$，还有一个质数模数 $p = 1000000007$。我们需要找到两个整数 $x$ 和 $y$，满足以下所有条件：

1. $0 \le x \le y < p$
2. $(x + y) \pmod p = b$
3. $(x \times y) \pmod p = c$

如果能找到这样的一对 $(x, y)$，就按照 $x$ 小 $y$ 大的顺序输出它们。如果找不到，就输出 -1 -1，呐。

举个栗子：如果 $b=3, c=2$，那么 $x=1, y=2$ 就是一组解，因为 $(1+2) \pmod p = 3$ 并且 $(1 \times 2) \pmod p = 2$。

解题思路分析

看到“两数之和”与“两数之积”，master有没有觉得很熟悉呀？这不就是韦达定理嘛！喵~

如果 $x$ 和 $y$ 是某个一元二次方程 $t^2 - (\text{和})t + (\text{积}) = 0$ 的两个根，那么它们的和就是 $x+y$，积就是 $x \cdot y$。

根据题目给的条件，我们马上就能构造出这个方程啦：

$$t^2 - bt + c \equiv 0 \pmod p$$

现在问题就变成了，解出这个在模 $p$ 意义下的一元二次方程的根 $t$。这两个根就是我们要找的 $x$ 和 $y$！

对于普通的一元二次方程 $at^2+bt+c=0$，我们有万能的求根公式：

$$t = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

在我们的方程 $t^2 - bt + c \equiv 0 \pmod p$ 中，$a=1$，一次项系数是 $-b$，常数项是 $c$。代入求根公式，就得到：

$$t \equiv \frac{-(-b) \pm \sqrt{(-b)^2 - 4(1)(c)}}{2(1)} \pmod p$$

整理一下就是：

$$t \equiv \frac{b \pm \sqrt{b^2 - 4c}}{2} \pmod p$$

所有运算都是在模 $p$ 意义下进行的哦。

为了解出 $t$，我们需要解决两个小问题：

1. 模意义下的除法：除以2，其实就是乘以2在模 $p$ 意义下的逆元。因为 $p=1000000007$ 是个奇质数，所以2的逆元 $2^{-1}$ 一定存在。根据费马小定理，$a^{p-2} \equiv a^{-1} \pmod p$，所以 $2^{-1} \equiv 2^{p-2} \pmod p$。一个更简单的算法是，因为 $p$ 是奇数，$p+1$ 是偶数，所以 $2 \times \frac{p+1}{2} = p+1 \equiv 1 \pmod p$，所以 $2$ 的逆元就是 $(p+1)/2$ 啦。

2. 模意义下的开方：这是本题最核心的难点，喵！我们需要计算 $\sqrt{b^2 - 4c} \pmod p$。这个问题被称为“求解二次剩余”。

我们令判别式 $\Delta = (b^2 - 4c) \pmod p$。现在我们的任务就是找到一个数 $s$，使得 $s^2 \equiv \Delta \pmod p$。

首先，怎么判断 $\Delta$ 在模 $p$ 意义下到底能不能开方呢？

• 如果 $\Delta = 0$，那它的平方根就是 $0$ 啦。这时候两个根相等，$x=y=(b \cdot 2^{-1}) \pmod p$。
• 如果 $\Delta \neq 0$，我们可以用欧拉判别准则来判断。对于奇质数 $p$，如果 $\Delta^{(p-1)/2} \equiv 1 \pmod p$，那么 $\Delta$ 就是一个二次剩余，它有两个平方根（互为相反数）。如果 $\Delta^{(p-1)/2} \equiv -1 \pmod p$，那么 $\Delta$ 就是一个二次非剩余，它没有平方根。如果出现这种情况，方程无解，我们就要输出 -1 -1。

判断完之后，如果存在解，我们该如何求出这个平方根 $s$ 呢？这里我要介绍一个非常神奇的算法——Cipolla 算法！(听起来就很高大上对不对，喵~)

Cipolla 算法的奇妙之旅

Cipolla 算法是一种随机算法，但它非常高效，思想也很有趣。它的核心是：如果在我们当前的世界（数域 $\mathbb{F}_p$）里解决不了问题，我们就扩展出一个更广阔的世界（扩域 $\mathbb{F}_{p^2}$）！

1. 寻找一个“非卖品”：我们首先要随机找一个数 $a$，使得 $a^2 - \Delta$ 是一个二次非剩余。也就是说，$(a^2 - \Delta)^{(p-1)/2} \equiv -1 \pmod p$。因为二次非剩余在模 $p$ 的数里大约占了一半，所以我们随机尝试几次就能很快找到这样的 $a$。

2. 创造新的“虚数单位”：我们定义一个新的“虚数单位” $\omega$，使得 $\omega^2 \equiv a^2 - \Delta \pmod p$。于是我们创造了一个新的数域，里面的数都可以写成 $A + B\omega$ 的形式（其中 $A, B$ 都是模 $p$ 意义下的数）。这和我们从实数扩展到复数是不是很像呀？

3. 施展魔法咒语：Cipolla 算法最神奇的地方来啦！它告诉我们，$\Delta$ 的一个平方根 $s$ 就是：

   $$s \equiv (a + \omega)^{(p+1)/2} \pmod p$$

   这个式子的计算需要用到我们刚才定义的复数乘法和快速幂。计算出来的结果 $(a+\omega)^{(p+1)/2}$ 会是一个实部不为0，虚部为0的数，它的实部就是我们梦寐以求的平方根 $s$！

是不是很神奇？这个结论的证明有点小复杂，但大致思路是利用了扩域 $\mathbb{F}_{p^2}$ 的性质和费马小定理在扩域上的推广。有兴趣的 master可以深入研究一下哦~

总结一下解题步骤

1. 读入 $b$ 和 $c$。
2. 计算判别式 $\Delta = (b^2 - 4c) \pmod p$。注意处理负数，可以 (b*b % p - 4*c % p + p) % p。
3. 使用 Cipolla 算法计算 $\Delta$ 的模 $p$ 平方根 $s$。
   • 如果 Cipolla 算法告诉我们无解（即 $\Delta$ 是二次非剩余），则输出 -1 -1。
4. 如果找到了平方根 $s$，计算 $2$ 的逆元 inv2 = (p+1)/2。
5. 计算方程的两个根：
   • $x_1 = (b + s) \cdot \text{inv2} \pmod p$
   • $x_2 = (b - s) \cdot \text{inv2} \pmod p$
6. 将 $x_1, x_2$ 从小到大排序，得到最终的 $x$ 和 $y$，然后输出。

好啦，思路已经很清晰了，让我们一起把代码变出来吧！喵~

代码实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib> // For rand()
#include <ctime>   // For srand()

// 使用 long long 防止计算过程中溢出
using ll = long long;

// 题目给定的模数
const ll P = 1000000007;

// 定义一个在模 P 意义下的复数结构体，用于 Cipolla 算法
struct Complex {
    ll real, imag;
};

// 全局变量，用于存储 Cipolla 算法中虚数单位的平方
ll omega_squared;

// 复数乘法 (A + Bw) * (C + Dw)
Complex multiply(Complex c1, Complex c2) {
    Complex res;
    // (ac + bdw^2) % P
    res.real = (c1.real * c2.real % P + c1.imag * c2.imag % P * omega_squared % P) % P;
    // (ad + bc)w % P
    res.imag = (c1.real * c2.imag % P + c1.imag * c2.real % P) % P;
    return res;
}

// 针对复数的快速幂
Complex complex_power(Complex base, ll exp) {
    Complex res = {1, 0}; // 初始值为 1 (1 + 0w)
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = multiply(res, base);
        }
        base = multiply(base, base);
        exp /= 2;
    }
    return res;
}

// 普通的整数快速幂，用于计算欧拉判别准则
ll power(ll base, ll exp) {
    ll res = 1;
    base %= P;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = res * base % P;
        }
        base = base * base % P;
        exp /= 2;
    }
    return res;
}

// Cipolla 算法，求解 x^2 = n (mod P)
ll cipolla(ll n) {
    n = (n % P + P) % P;
    if (n == 0) return 0;

    // 欧拉判别准则：检查 n 是否是二次剩余
    // n^((P-1)/2) % P == 1  => 是二次剩余
    // n^((P-1)/2) % P == -1 (即 P-1) => 是二次非剩余
    if (power(n, (P - 1) / 2) == P - 1) {
        return -1; // 无解
    }

    // 随机寻找一个 a，使得 a^2 - n 是二次非剩余
    ll a;
    while (true) {
        a = rand() % P;
        omega_squared = (a * a % P - n + P) % P;
        if (power(omega_squared, (P - 1) / 2) == P - 1) {
            break; // 找到了！
        }
    }

    // 计算 (a + w)^((P+1)/2)，结果的实部就是 n 的一个平方根
    Complex base = {a, 1};
    Complex res = complex_power(base, (P + 1) / 2);
    
    return res.real;
}

void solve() {
    ll b, c;
    std::cin >> b >> c;

    // 确保 b 和 c 都在 [0, P-1] 范围内
    b = (b % P + P) % P;
    c = (c % P + P) % P;

    // 计算判别式 Delta = b^2 - 4c (mod P)
    ll delta = (b * b % P - 4 * c % P + P) % P;

    // 用 Cipolla 算法求解 delta 的模平方根
    ll sqrt_delta = cipolla(delta);

    if (sqrt_delta == -1) {
        // 无解
        std::cout << "-1 -1\n";
    } else {
        // 计算 2 的逆元
        ll inv2 = (P + 1) / 2;
        
        // 根据求根公式计算两个根
        ll x1 = (b + sqrt_delta) % P * inv2 % P;
        ll x2 = (b - sqrt_delta + P) % P * inv2 % P;

        // 保证 x <= y
        if (x1 > x2) {
            std::swap(x1, x2);
        }
        std::cout << x1 << " " << x2 << "\n";
    }
}

int main() {
    // 加速输入输出
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 设置随机数种子，让每次运行的 rand() 不同
    srand(time(0));

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(\log P)$ 对于每组测试数据，主要的计算开销在 Cipolla 算法中。Cipolla 算法包含一个随机查找 a 的循环和一个快速幂。

  • 随机查找 a：由于二次非剩余大约占所有数的一半，期望查找次数是常数级别的（约2次）。
  • 欧拉判别准则和复数快速幂：这两个操作都是基于快速幂的，其时间复杂度为 $O(\log P)$。 因此，每组测试数据的总时间复杂度是 $O(\log P)$。

• 空间复杂度: $O(1)$ 我们只使用了几个变量来存储中间结果，没有使用与输入规模 $P$ 相关的额外数组或数据结构，所以空间复杂度是常数级别的，喵~

知识点总结

1. 韦达定理: 将“和与积”问题转化为解一元二次方程。
2. 模运算: 所有的计算都在模 $p$ 的有限域下进行，要注意负数的处理（加上模数再取模）。
3. 模逆元: 在模运算中，除以一个数等于乘以它的逆元。对于质数模 $p$，a的逆元可以通过费马小定理 $a^{p-2}$ 计算，或者对于特定的数（如2）可以找巧。
4. 二次剩余: 核心概念，即模意义下的平方根。
5. 欧拉判别准则: 一个高效判断一个数是否是二次剩余的方法。
6. Cipolla 算法: 求解二次剩余的强大（而且很酷）的随机算法。它的思想是通过扩域来解决原域中的问题，是数论中一个非常漂亮的方法，值得 master 学习和掌握哦！

希望这篇题解能帮助到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！