洛谷P8814（2022年CSP-J）题解：数学推导与C++实现

一、题目解读

本题考察RSA加密算法的数学基础，给定n、d、e三个参数，要求还原出构成RSA密钥的两个质数p和q。核心难点在于如何通过n-e*d+2推导出p+q，再利用二次方程求解质数对。

二、解题思路

1. 数学推导：利用RSA算法中φ(n)=(p-1)(q-1)的性质，结合n=pq和ed≡1 mod φ(n)的关系，推导出p+q = n - e*d + 2

2. 方程求解：将问题转化为解二次方程x² - (p+q)x + n = 0

3. 判别式验证：通过计算判别式delta确保存在实数解

4. 整数验证：检查解是否为整数且满足原始条件

三、解题步骤

1. 计算中间值m = n - e*d + 2

2. 计算判别式delta = m² - 4n

3. 验证delta是否为完全平方数

4. 求解二次方程得到p和q

5. 验证pq==n且(p-1)(q-1)+1==ed

四、完整代码与注释

#include <iostream>
#include <cmath>
using namespace std;

void solve() {
    long long k, n, d, e;
    cin >> k;
    while (k--) {
        cin >> n >> d >> e;
        long long m = n - e * d + 2; // 计算p+q
        long long delta = m * m - 4 * n; // 计算判别式
        
        if (delta < 0) {
            cout << "NO\n";
            continue;
        }
        
        long long sqrt_delta = sqrt(delta);
        if (sqrt_delta * sqrt_delta != delta) {
            cout << "NO\n";
            continue;
        }
        
        long long p = (m - sqrt_delta) / 2;
        long long q = (m + sqrt_delta) / 2;
        
        if (p > 0 && q > 0 && p * q == n && (p-1)*(q-1)+1 == e*d) {
            cout << p << " " << q << "\n";
        } else {
            cout << "NO\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

五、总结

本解法通过严谨的数学推导将RSA分解问题转化为二次方程求解，代码实现中特别处理了边界条件和验证逻辑。算法时间复杂度为O(k)，空间复杂度O(1)，能高效处理大规模输入。