【CSP】CSP-J 2022真题 | 乘方 luogu-P8813 (适合GESP二级及以上考生练习)

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

P8814 [CSP-J 2022] 解密

题目要求

题目描述

给定一个正整数 ，有  次询问，每次给定三个正整数 ，求两个正整数 ，使 、。

输入格式

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

接下来  行，第  行三个正整数 。

输出格式

输出  行，每行两个正整数  表示答案。

为使输出统一，你应当保证 。

如果无解，请输出 NO。

输入输出样例 #1

输入 #1

10770 77 5633 1 211545 1 499683 3 227858 3 257723 37 13572 26 11867 17 17829 3 263528 4 109

输出 #1

2 385NONONO11 783 2412 286NONO6 88

说明/提示

【数据范围与约定】

以下记 。

保证对于  的数据，，对于任意的 ，，，。

题目分析

本题给出了包含两个未知数  和  的方程组，要求我们根据已知的  求解符合条件的  和 。由于数据范围中 ，如果使用暴力枚举因数的方式求解，时间复杂度会达到 ，显然会超时。因此我们需要更高效的求解方法。

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

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

已知方程组为：

展开方程 ②：

将方程 ① 中的  代入上式：

变形可得  的表达式：

为了书写简便，我们令 。结合题目已有的方程，我们可以构建一个新的方程组：

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

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

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

利用求根公式，可得：

因为题目要求 ，所以：

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

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

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

3. 解法二：二分答案法

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

由于 ，且 ，我们可以确定  的取值范围在  之间。

在这段区间内，随着  的增大，乘积  是严格单调递增的。 因此，我们可以在  内二分查找 ：

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

二分查找每次询问的时间复杂度为 ，总时间复杂度为 。在  的情况下，总计算次数约为  次，完全可以在时限内通过。

示例代码

方法一：求根公式法（）

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

#include<iostream>#include<cmath>voidsolve(){    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";}intmain(){    // 优化输入输出流性能    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int k;    std::cin >> k;    while (k--) {        solve();    }    return 0;}

方法二：二分答案法（）

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

#include<iostream>voidsolve(){    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";    }}intmain(){    // 优化输入输出流性能    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int k;    std::cin >> k;    while (k--) {        solve();    }    return 0;}

结语

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

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

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