2022真题 | 解密 luogu-P8814

CSP-J 2022真题-解密，是一道结合数学推导与数值运算的经典题目。本题可以通过将方程组转化为一元二次方程，利用求根公式在 $O(1)$ 的时间内求解；也可以利用单调性通过二分法进行求解。适合 GESP 四级及以上考生练习，难度⭐⭐，洛谷难度等级普及-。

P8814 [CSP-J 2022] 解密

题目要求

题目描述

给定一个正整数 $k$，有 $k$ 次询问，每次给定三个正整数 $n_i, e_i, d_i$，求两个正整数 $p_i, q_i$，使 $n_i = p_i \times q_i$、$e_i \times d_i = (p_i - 1)(q_i - 1) + 1$。

输入格式

第一行一个正整数 $k$，表示有 $k$ 次询问。

接下来 $k$ 行，第 $i$ 行三个正整数 $n_i, d_i, e_i$。

输出格式

输出 $k$ 行，每行两个正整数 $p_i, q_i$ 表示答案。

为使输出统一，你应当保证 $p_i \leq q_i$。

如果无解，请输出 NO。

输入输出样例 #1

输入 #1

10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109

输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

说明/提示

【数据范围与约定】

以下记 $m = n - e \times d + 2$。

保证对于 $100\%$ 的数据，$1 \leq k \leq {10}^5$，对于任意的 $1 \leq i \leq k$，$1 \leq n_i \leq {10}^{18}$，$1 \leq e_i \times d_i \leq {10}^{18}$，$1 \leq m \leq {10}^9$。

题目分析

本题给出了包含两个未知数 $p$ 和 $q$ 的方程组，要求我们根据已知的 $n, e, d$ 求解符合条件的 $p$ 和 $q$。由于数据范围中 $k \le 10^5$，如果使用暴力枚举因数的方式求解，时间复杂度会达到 $O(k \sqrt{n})$，显然会超时。因此我们需要更高效的求解方法。

1. 代数变形与方程组构建

首先，我们对方程组进行展开与化简。

已知方程组为：

展开方程 2：

将方程 (1) 中的 $n = p \times q$ 代入上式：

变形可得 $p + q$ 的表达式：

为了书写简便，我们令 $m = p + q = n - e \times d + 2$。结合题目已有的方程，我们可以构建一个新的方程组：

这变成了经典的“已知两数之和与两数之积，求解这两数”的问题。

2. 解法一：一元二次方程求根公式（推荐）

根据韦达定理，$p$ 和 $q$ 可以看作是关于 $x$ 的一元二次方程的两个实数根：

利用求根公式，可得：

因为题目要求 $p \le q$，所以：

求解时的判定与注意事项：

1. 无实数解判定： 若判别式 $\Delta = m^2 - 4n < 0$，方程无实数解，输出 NO。
2. 整数解判定：
   • 判别式 $\Delta$ 必须是完全平方数。我们可以计算 $r = \lfloor \sqrt{\Delta} \rfloor$（或使用四舍五入 round(sqrt(delta))），并校验是否满足 $r \times r == \Delta$。如果不满足，说明 $\sqrt{\Delta}$ 不是整数，即无整数解。
   • 分子 $m - r$ 和 $m + r$ 必须是偶数，即满足 $(m - r) \pmod 2 == 0$。如果不能整除，也说明无整数解。
3. 数据溢出预防： 虽然提示中 $m \le 10^9$，但 $m^2$ 的范围可达 $10^{18}$，$n$ 的范围可达 $10^{18}$。在 C++ 中，我们必须使用 long long 类型来承载所有的计算，以防止数值溢出。

该方法单次查询的时间复杂度为 $O(1)$，总时间复杂度为 $O(k)$，执行效率非常高。

3. 解法二：二分答案法

如果不想使用浮点数开方函数 sqrt()，也可以利用单调性采用二分查找。

由于 $p + q = m$，且 $p \le q$，我们可以确定 $p$ 的取值范围在 $[1, \lfloor m / 2 \rfloor]$ 之间。

在这段区间内，随着 $p$ 的增大，乘积 $p \times (m - p)$ 是严格单调递增的。 因此，我们可以在 $[1, m/2]$ 内二分查找 $p$：

• 设当前二分区间的中点为 mid，计算乘积 val = mid * (m - mid)。
• 若 val == n，说明找到了符合条件的整数解，此时 $p = \mathrm{mid}$，$q = m - \mathrm{mid}$。
• 若 val < n，说明当前的 mid 偏小，应向右半区间继续查找，令 L = mid + 1。
• 若 val > n，说明当前的 mid 偏大，应向左半区间继续查找，令 R = mid - 1。

二分查找每次询问的时间复杂度为 $O(\log m)$，总时间复杂度为 $O(k \log m)$。在 $k = 10^5, m = 10^9$ 的情况下，总计算次数约为 $3 \times 10^6$ 次，完全可以在时限内通过。

示例代码

方法一：求根公式法（$O(1)$）

以下是使用一元二次方程求根公式实现的 C++ 代码。

#include <iostream>
#include <cmath>

void solve() {
    long long n, d, e;
    std::cin >> n >> d >> e;

    // 根据推导，m = p + q
    long long m = n - e * d + 2;

    // 计算判别式 delta = m^2 - 4n
    long long delta = m * m - 4 * n;

    // 如果判别式小于 0，无实数解
    if (delta < 0) {
        std::cout << "NO\n";
        return;
    }

    // 对方程求根，并校验是否为完全平方数
    long long r = std::round(std::sqrt(delta));
    if (r * r != delta) {
        std::cout << "NO\n";
        return;
    }

    // 校验分子是否为偶数，即是否能被 2 整除
    if ((m - r) % 2 != 0) {
        std::cout << "NO\n";
        return;
    }

    // 计算 p 和 q
    long long p = (m - r) / 2;
    long long q = (m + r) / 2;

    // 校验 p 和 q 是否为正整数
    if (p <= 0 || q <= 0) {
        std::cout << "NO\n";
        return;
    }

    std::cout << p << " " << q << "\n";
}

int main() {
    // 优化输入输出流性能
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    return 0;
}

方法二：二分答案法（$O(\log m)$）

以下是使用二分查找实现的 C++ 代码。

#include <iostream>

void solve() {
    long long n, d, e;
    std::cin >> n >> d >> e;

    // 根据推导，m = p + q
    long long m = n - e * d + 2;

    // 二分区间 p <= q，且 p + q = m，因此 p 必然在 [1, m / 2]
    long long L = 1, R = m / 2;
    long long p = -1;

    while (L <= R) {
        long long mid = L + (R - L) / 2;
        long long val = mid * (m - mid);

        if (val == n) {
            p = mid;
            break; // 找到答案，退出二分
        } else if (val < n) {
            L = mid + 1; // 乘积偏小，增大 p
        } else {
            R = mid - 1; // 乘积偏大，减小 p
        }
    }

    // 如果没有找到解
    if (p == -1) {
        std::cout << "NO\n";
    } else {
        long long q = m - p;
        std::cout << p << " " << q << "\n";
    }
}

int main() {
    // 优化输入输出流性能
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    return 0;
}

结语

本题的核心突破口在于对方程组的展开和化简。通过代数变形，将复杂的乘积方程转化为了已知和与积的经典二次方程 model。在实战中，熟练掌握这类代数变形技巧以及边界和精度的合理校验，是快速且准确地解决数学类算法题目的关键。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号