P8814 [CSP-J 2022] 解密题解

· · 题解

前置知识

整式的加减乘除 —— 初一

思路

看到题目先下意识进行化简 ed：

ed = (p-1)(q-1) + 1

化简得：

ed = pq - p - q + 1+ 1

将 n = pq 带入原式得：

ed = n - p - q + 2

整理原式得

p + q = n - ed + 2

插句闲话

我们把目光聚焦到题面的数据范围一栏，看到这句话

”以下记 m = n - ed + 2。“

正好是化简后的 p + q。

我当时看到这句话就知道，我的解法是正确的！

话说回来

现在已知

\begin{cases} p + q = n - ed + 2\\ pq = n \end{cases}

要求 p、q。

其中 n,e,d 为常数。

如果我们能推出 p - q，那么问题就迎刃而解了。

初一党是不是熟悉了起来？

忘了？不要紧，我们来复习一下。

完全平方和：(a + b)^2 = a^2 + 2ab + b^2

完全平方差：(a - b)^2 = a^2 - 2ab + b^2

现在已知 ab，a + b，我们如何求出 a - b 呢？

我们来把完全平方和减去完全平方差试试：

(a + b)^2 - (a - b)^2 = (a^2 + 2ab + b^2) - (a^2 -2ab + b^2)

等号右边化简得：

(a + b)^2 - (a - b)^2 = a^2 + 2ab + b^2 - a^2 +2ab - b^2

合并同类项得：

(a + b)^2 - (a - b)^2 = 4ab

挪一挪项得：

(a + b)^2 - 4ab = (a - b)^2

交换左右两边得：

(a - b)^2 = (a + b)^2 - 4ab

左边脱掉平方得：

a - b = \pm \sqrt{(a + b)^2 - 4ab}

已知 ab 即 pq，a + b 即 p + q，就能求出 a-b 即 p - q 了！

补充解释

由于 p 与 q 的大小关系无关紧要——题目中只说了打印 p 与 q 两者中较大的再打印两者中较小的。p 我们在这里先假设它为 p 与 q 两者中较大的数，q 为 p 与 q 中的较小数，因此下文中 p - q 没有正负号。

将 n = pq，n - e \times d + 2 = p + q 带入得：

\begin{cases} p + q = n - ed + 2\\ p - q = \sqrt{(n - ed + 2)^2 - 4n} \end{cases}

我们设上面一行为 1 式，下面一行为 2 式，我们将 1 式 + 2 式得到的 3 式为：

2p = n - ed + 2 + \sqrt{(n - ed + 2)^2 - 4n}

等式两边同除以2得：

p = \frac{n - ed + 2 + \sqrt{(n - ed + 2)^2 - 4n}}{2}

将 1 式做个小小的变动得：

q = n - ed + 2 - p

此时 p 是已知的，n - e \times d + 2 为常数，所以可以解出 q 为：

q = n - ed + 2 - \frac{n - ed + 2 + \sqrt{(n - ed + 2)^2 - 4n}}{2}

这里可以化简得：

q = \frac{n - e \times d + 2 -\sqrt{(n - e \times d + 2)^2 - 4n}}{2}

最终得：

\begin{cases} p = \frac{n - ed + 2 + \sqrt{(n - ed + 2)^2 - 4n}}{2}\\ q = \frac{n - ed + 2 -\sqrt{(n - ed + 2)^2 - 4n}}{2} \end{cases}

再看到题目要求，p、q 要求是正整数。因为我们知道，如果平方根不是正数，只可能是 0、正有理数、无理数（平方开不尽）、不在实数范围内的虚数（被开方数小于 0）。

0 好办，我们只需要算出 p 和 q 之后特判就可以了。对于小数和无理数，我们可以先用 long long 强制转换，舍弃小数点后带入题目给出的两个式子，检验解是否正确。对于虚数，函数 sqrt 的被开方数为负数的时候会返回 NaN，用 long long 储存 NaN 时值为 0，和我们处理 P = 0 时思路一样。如果解符合上述条件，那么一定是整数，也就是符合题目要求的解。

那时间复杂度如何保证呢？加减乘除运算都是 O(1) 的，sqrt 函数也是 O(1) 级别的，故单次询问时间复杂度为 O(1)，总询问复杂度为 O(k)，最大运算量为 10^5，故能轻松通过此题。

思路部分完结撒花！

代码

//
//  main.cpp
//  P8814 [CSP-J 2022] 解密（民间数据）
//
//  Created by SkyWave Sun on 2022/11/7.
//

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

int main(int argc, const char * argv[]) {
    long long k;
    scanf("%lld",&k);
    while (k--) {
        long long n,e,d;
        scanf("%lld%lld%lld",&n,&e,&d);
        long long PsubQ = sqrt((n - e * d + 2) * (n - e * d + 2) - (n * 4));
        long long PaddQ = n - e * d + 2;
        long long P = (PsubQ + PaddQ) / 2;
        long long Q = PaddQ - P;
        if (P * Q == n && e * d == (P - 1) * (Q - 1) + 1 && P && Q) {
            printf("%lld %lld\n",min(P, Q),max(P, Q));
        }else {
            printf("NO\n");
        }
    }
    return 0;
}

完结撒花！

我是 SkyWave，这是我的第三篇题解，有不足之处请多多指出，有任何看不懂的地方欢迎留言或者私信！

更新日志：

（如有错误和不清楚的地方敬请指出，会立即更新）

一更

5 月 3 日下午 17:34 分

更新内容：

删除了“边上代码边讲”这句习惯性的废话。更改了 Q 的计算方式。将代码中的位移都替换成了除法。补充了对代码的解释便于读者更好理解。

补充说明：

事实上我一开始的 Q 就是通过 P + Q - P 算出的，只是因为想要验证题解中推导的部分有没有误所以将它改成用繁琐公式算，现在为了读者阅读方便已经改回。