[C++] 解密

发表于 更新于 分类于 ， ，

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

给定一个正整数 kk，有 kk 次询问，每次给定三个正整数 ni,ei,din_i, e_i, d_i，求两个正整数 pi,qip_i, q_i，使 ni=pi×qin_i = p_i \times q_i、ei×di=(pi−1)(qi−1)+1e_i \times d_i = (p_i - 1)(q_i - 1) + 1。

输入格式

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

接下来 kk 行，第 ii 行三个正整数 ni,di,ein_i, d_i, e_i。

输出格式

输出 kk 行，每行两个正整数 pi,qip_i, q_i 表示答案。

为使输出统一，你应当保证 pi≤qip_i \leq q_i。

如果无解，请输出 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+2m = n - e \times d + 2。

保证对于 100%100\% 的数据，1≤k≤1051 \leq k \leq {10}^5，对于任意的 1≤i≤k1 \leq i \leq k，1≤ni≤10181 \leq n_i \leq {10}^{18}，1≤ei×di≤10181 \leq e_i \times d_i \leq {10}^{18}
，1≤m≤1091 \leq m \leq {10}^9。

| 测试点编号 | k≤k \leq | n≤n \leq | m≤m \leq | 特殊性质 |
| :------## --: | :—## : | :—## -: | :---------## : | :-------------: |
| 11 | 10310^3 | 10310^3 | 10310^3 | 保证有解 |
| 22 | 10310^3 | 10310^3 | 10310^3 | 无 |
| 33 | 10310^3 | 10910^9 | 6×1046\times 10^4 | 保证有解 |
| 44 | 10310^3 | 10910^9 | 6×1046\times 10^4 | 无 |
| 55 | 10310^3 | 10910^9 | 10910^9 | 保证有解 |
| 66 | 10310^3 | 10910^9 | 10910^9 | 无 |
| 77 | 10510^5 | 101810^{18} | 10910^9 | 保证若有解则 p=qp=q |
| 88 | 10510^5 | 101810^{18} | 10910^9 | 保证有解 |
| 99 | 10510^5 | 101810^{18} | 10910^9 | 无 |
| 1010 | 10510^5 | 101810^{18} | 10910^9 | 无 |

题解

由题可知

ed=(p−1)(q−1)+1=pq−p−q+1+1=pq−p−q+2\begin{aligned} ed & = (p-1)(q-1)+1\\ & = pq-p-q+1+1 \\ & = pq-p-q+2 \end{aligned}

又因为 n=pqn = pq ，所以 ed=n−p−q+2ed = n - p - q + 2

又

m=n−ed+2=n−n+p+q−2+2=p+q\begin{aligned} m & = n - ed + 2\\ & = n - n + p + q -2 + 2\\ & = p + q \end{aligned}

所以

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

所以 m=n+2−edm = n + 2 - ed

因此可列关于 p,qp,q 的二元一次方程组（ n,mn, m 为已知）

{p+q=mpq=n\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=na = 1, b = -m, c = n ，即可求判别式 Δ=b2−4ac\Delta = b^2 - 4ac 。

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

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

既然我们得到了结论，就把计算过程实现以下，O(k)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;
}