这是一个典型的 暴力枚举（TLE） 版本代码。

TLE 原因分析

1. 算法思路：利用 $n = p \times q$，我们尝试枚举 $p$。因为 $p \le q$，所以 $p$ 的范围一定是 $1 \sim \sqrt{n}$。我们在循环中检查 $p$ 是否能整除 $n$，如果能，算出 $q = n/p$，再验证是否满足第二个条件 $e \times d = (p-1)(q-1)+1$。
2. 复杂度分析：
   • 单次询问的时间复杂度是 $O(\sqrt{n})$。
   • 题目中 $n$ 最大可达 $10^{18}$，所以 $\sqrt{n} = 10^9$。
   • 这意味着对于一个大的 $n$，循环需要执行 10亿次。
   • 题目有 $k$ 次询问（$k \le 10^5$）。如果运气不好，总运算次数会达到 $10^{14}$ 次。
   • 计算机 1 秒只能跑约 $10^8$ 次，这绝对会 超时 (Time Limit Exceeded)。

TLE 代码示例

#include <iostream>
using namespace std;

typedef long long ll;

void solve() {
    ll n, d, e;
    cin >> n >> d >> e;

    // 暴力枚举 p
    // p 的范围是从 1 到 sqrt(n)
    // 只要 n 很大（比如 10^18），这个循环就要跑 10^9 次 -> 必定超时
    for (ll p = 1; p * p <= n; p++) {
        
        // 1. 检查 p 是否是 n 的因数
        if (n % p == 0) {
            ll q = n / p;
            
            // 2. 检查是否满足第二个方程
            // e * d = (p - 1)(q - 1) + 1
            // 变形一下避免溢出或者直接算：
            // 检查 (p-1)*(q-1) + 1 是否等于 e*d
            if ((p - 1) * (q - 1) + 1 == e * d) {
                cout << p << " " << q << endl;
                return; // 找到了，直接输出并返回
            }
        }
    }

    // 循环跑完了都没找到
    cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int k;
    cin >> k;
    while (k--) {
        solve();
    }
    return 0;
}

预期结果

• 样例 1：可以很快通过，因为样例里的 $n$ 都很小（几百几千），循环几十次就结束了。
• 实际测试点：只要 $n$ 超过 $10^{10}$，这个程序就会卡死直到判题系统强制终止，获得 TLE。

这是一份标准的、符合 CSP-J 满分要求的 C++ 代码解答。

1. 数学推导过程

这道题的核心在于利用 韦达定理（或者简单的代数变形）构建一元二次方程。

已知：

1. $n = p \times q$
2. $e \times d = (p - 1)(q - 1) + 1$

我们将第 2 个式子展开：

代入 $n = pq$：

移项求 $(p+q)$：

令 $m = p + q$。 现在我们知道了 两数之和 $m$ 和 两数之积 $n$。根据韦达定理，$p$ 和 $q$ 是方程 $x^2 - mx + n = 0$ 的两个根。

利用求根公式：

即判别式 $\Delta = m^2 - 4n$。

2. 判断无解的条件

要使 $p, q$ 为正整数，必须满足：

1. 有实数根：$\Delta \ge 0$。
2. 根是整数（即完全平方数）：$\sqrt{\Delta}$ 必须是整数。
3. 分子是偶数：$(m - \sqrt{\Delta})$ 必须能被 2 整除（实际上若 $\Delta$ 是完全平方数，$m$ 和 $\sqrt{\Delta}$ 奇偶性一定相同，相减一定是偶数，所以这一步通常可以省略，但写上更保险）。

3. 标准 AC 代码

#include <iostream>
#include <cmath> // 用于 sqrt

using namespace std;

// 必须使用 long long，因为 n, e*d 可达 10^18
typedef long long ll;

void solve() {
    ll n, d, e;
    cin >> n >> d >> e;

    // 1. 计算 p + q 的值
    // p + q = n - e * d + 2
    ll m = n - e * d + 2;

    // 2. 计算判别式 delta = m^2 - 4n
    // 这里 m 和 n 很大，中间计算过程必须在 long long 范围内
    ll delta = m * m - 4 * n;

    // 3. 判断条件 A: delta 必须非负
    if (delta < 0) {
        cout << "NO" << endl;
        return;
    }

    // 4. 判断条件 B: delta 必须是完全平方数
    ll r = (ll)sqrt(delta); // 开根号取整
    if (r * r != delta) {
        cout << "NO" << endl;
        return;
    }

    // 5. 判断条件 C: (m - r) 必须能被 2 整除
    // 数学上，若 delta 是完全平方数，m^2 - 4n = r^2
    // m^2 和 r^2 同奇偶 -> m 和 r 同奇偶 -> m - r 必为偶数
    // 但为了逻辑严密，写上这个判断也无妨
    if ((m - r) % 2 != 0) {
        cout << "NO" << endl;
        return;
    }

    // 6. 计算 p 和 q
    // 题目要求 p <= q，所以 p 取减号，q 取加号
    ll p = (m - r) / 2;
    ll q = (m + r) / 2;

    cout << p << " " << q << endl;
}

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    return 0;
}

4. 关键点总结

1. 数据类型：全程使用 long long。虽然 $n$ 很大，但题目保证了 $m \le 10^9$，这意味着 $m^2$ 最多 $10^{18}$，刚好在 long long 的范围内，不会溢出。
2. 精度问题：在使用 sqrt 时，对于 $10^{18}$ 级别的数，double 的精度（约 15-16 位有效数字）通常是足够的，因为完全平方数之间的间隔在 $10^9$ 附近非常大，远超精度误差。所以直接 (long long)sqrt(delta) 然后回乘验证 r*r == delta 是安全的。
3. 推导逻辑：这道题不能用二分查找（虽然也可以做，但数学公式是 $O(1)$ 的），直接利用数学公式推导是最优解。

你好！我是你的 OI 教练。

这道题（CSP-J 2022 T2）是一道非常典型的数学推导题。数据范围 $n \le 10^{18}$ 告诉你：任何形式的暴力枚举（哪怕是 $O(\sqrt{n})$ 的枚举）都会超时。这道题要求你通过数学公式，$O(1)$ 地算出每一次询问的答案。

下面是解题的几个关键线索，请顺着我的思路往下想：

1. 核心突破口：化简公式

题目给了两个等式：

1. $n = p \times q$
2. $e \times d = (p - 1)(q - 1) + 1$

请尝试把第 2 个式子展开一下：

既然你知道 $n = pq$，能不能把 $n$ 代入进去？ 一旦代入，你会发现你可以求出 $p + q$ 的值。 我们令 $m = p + q$，请你推导出 $m$ 等于什么表达式（用 $n, e, d$ 表示）。

2. 韦达定理（或者一元二次方程）

现在你手头有两个关键信息：

1. 你知道了 $p \times q = n$ （两数之积）
2. 你知道了 $p + q = m$ （两数之和，由步骤 1 算出）

这就变成了小学/初中数学经典的**“知和求积”**问题。 构造一个关于 $x$ 的一元二次方程：

也就是：

这个方程的两个根，正好就是 $p$ 和 $q$。

3. 求解与判断（判别式 $\Delta$）

直接使用求根公式：

代入我们的系数，就是：

你需要解决的问题是：什么时候输出 NO？ 根据题目要求 $p, q$ 必须是正整数，你需要检查以下几点：

1. 根号下必须是非负数：$\Delta = m^2 - 4n$ 必须 $\ge 0$。
2. 必须是完全平方数：$\sqrt{\Delta}$ 必须得是一个整数。如果开根号开不尽，说明 $p, q$ 是无理数，不合题意。
   • 编程提示：long long r = sqrt(delta); if (r * r != delta) ...
3. 分子必须是偶数：$(m \pm \sqrt{\Delta})$ 必须能被 2 整除，否则 $p, q$ 就是小数（例如 2.5），也不合题意。

4. 也是最重要的：数据类型

看一下数据范围：$n \le 10^{18}$。

• 所有的变量（$n, e, d, p, q, m$ 以及中间计算的 $\Delta$）都必须使用 long long。
• 虽然 $n$ 很大，但题目保证了 $m \le 10^9$，所以 $m^2$ 最多是 $10^{18}$，刚好在 long long 范围内，不会溢出。

代码逻辑框架：

// 1. 读入 k
// 2. 循环 k 次：
    // a. 读入 n, d, e
    // b. 计算和 m = n - e * d + 2
    // c. 计算判别式 delta = m * m - 4 * n
    // d. 检查 delta 是否 < 0
    // e. 计算 r = sqrt(delta)
    // f. 检查 r * r 是否等于 delta (判断是否完全平方)
    // g. 检查 (m - r) 是否是偶数 (判断能否被2整除)
    // h. 如果以上都通过，输出较小的解 (m - r) / 2 和较大的解 (m + r) / 2
    // i. 否则输出 NO

这道题其实就是考数学公式的推导，只要推出来就是简单的计算。加油！