2022 CCF CSP-J2 解密

给定一个正整数$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\le q_i$。

如果无解，请输出 NO。

数据范围
以下记 $m=n-e\times d+2$。
保证对于 $100\%$ 的数据，$1\le k\le 10^5$，对于任意的 $1\le i\le k$，$1\le n_i\le 10^{18}$，$1\le e_i\times d_i\le 10^{18}$，$1\le m\le 10^9$。

输入样例：

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
3
4
5
6
7
8
9
10
11

输出样例：

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
1
2
3
4
5
6
7
8
9
10

C++代码

#include
typedef long long LL;

using namespace std;

int main() {
    int tt;
    cin >> tt;
    
    while(tt --) {
        LL n, c, d, p, q;
        //n = p * q
        //c * d = p * q - p - q + 2
        //c * d = n - p - q + 2
        //t = c * d
        //p + q = n - t + 2
        //p * q = n
        cin >> n >> c >> d;
        LL t = c * d;
        LL s = n - t + 2;//p + q
        LL x = s * s;//(p + q) ^ 2
        LL y = x - 4 * n;//(p - q) ^ 2
        
        LL z = LL(sqrt(y));//|p - q|
        if(z * z != y) cout << "NO" << '\n';
        else {
            p = (s + z) / 2;
            q = (s - z) / 2;
            if(p > q) swap(p, q);
            cout << p << " " << q << '\n';
        }
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35