[C++] 解密

发表于 更新于

P8814 [CSP-J 2022] 解密 - 洛谷

给定一个正整数 k，有 k 次询问，每次给定三个正整数 ni, ei, di，求两个正整数 pi, qi，使 ni = pi × qi、ei × di = (pi − 1)(qi − 1) + 1。

输入格式

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

接下来 k 行，第 i 行三个正整数 ni, di, ei。

输出格式

输出 k 行，每行两个正整数 pi, qi 表示答案。

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

如果无解，请输出 NO。

输入输出样例 #1

输入 #1

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

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

说明/提示

【样例 #2】

见附件中的 decode/decode2.in 与 decode/decode2.ans。

【样例 #3】

见附件中的 decode/decode3.in 与 decode/decode3.ans。

【样例 #4】

见附件中的 decode/decode4.in 与 decode/decode4.ans。

【数据范围】

以下记 m = n − e × d + 2。

保证对于 100% 的数据，1 ≤ k ≤ 105，对于任意的 1 ≤ i ≤ k，1 ≤ ni ≤ 1018，1 ≤ ei × di ≤ 1018 ，1 ≤ m ≤ 109。

测试点编号 k≤ n≤ m≤ 特殊性质
1 103 103 103 保证有解
2 103 103 103 无
3 103 109 6 × 104 保证有解
4 103 109 6 × 104 无
5 103 109 109 保证有解
6 103 109 109 无
7 105 1018 109 保证若有解则 p = q
8 105 1018 109 保证有解
9 105 1018 109 无
10 105 1018 109 无

题解

由题可知
$$ \begin{aligned} ed & = (p-1)(q-1)+1\\ & = pq-p-q+1+1 \\ & = pq-p-q+2 \end{aligned} $$
又因为 n = pq ，所以 ed = n − p − q + 2

又
$$ \begin{aligned} m & = n - ed + 2\\ & = n - n + p + q -2 + 2\\ & = p + q \end{aligned} $$
所以
$$ \begin{aligned} ed & = n - (p+q) + 2\\ & = n - m + 2 \end{aligned} $$
所以 m = n + 2 − ed

因此可列关于 p, q 的二元一次方程组（ n, m 为已知）
$$ \begin{cases} p + q = m\\ pq = n \end{cases} $$

解：
$$ \begin{align} p = \frac n q\\ \frac n q + q = m\\ n + q^2 = mq\\ q^2 - mq + n = 0 \end{align} $$

得到一个一元二次方程，其中 a = 1, b =  − m, c = n ，即可求判别式 Δ = b2 − 4ac 。

若 Δ ≥ 0 ，则有解，套用一元二次方程求根公式 $q = \frac {-b \pm \sqrt {\Delta}} {2a}$ 中较大那个（即 $q = \frac {-b + \sqrt {\Delta}} {2a}$）即可。

然后计算 $p = \frac n q$ 即可。

既然我们得到了结论，就把计算过程实现以下，O(k) 复杂度解决。

注意：一定要用long long或者int64_t，不然会溢出！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int main(){
    int k;
    cin >> k;
    
    while(k--){
        int64_t n, e, d;
        cin >> n >> e >> d;
        int64_t m = n + 2 - e*d;
        int64_t delta = m*m - 4*n;
        int64_t sd = (delta>=0?sqrt(delta):-1);
        if(sd<0 || sd*sd != delta) {
            cout << "NO" << endl;
            continue;
        }
        int64_t q = (m+sd)/2;
        int64_t p = n/q;
        cout << p << " " << q << endl;
    }
    
    return 0;
}