题目：

[CSP-J 2022] 解密

[CSP-J 2022] 解密

前置知识

整式的加减乘除 —— 初一

题目解析

尽管我没有参加比赛

但我做这道题看到

$$n_i = p_i \times q_i, \: e_i \times d_i = (p_i - 1)(q_i - 1) + 1$$

首先化简$ed$:

$$e_i \times d_i = (p_i - 1)(q_i - 1) + 1$$

化简得到:

$$ed = pq - p - q + 2$$

将$n = p \times q$带入原式可得:

$$ed = n - p - q + 2$$

整理原式可得:

$$p + q = n - ed + 2$$

已知：

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

要求 $p, q$。

其中 $n, e, d$ 为常数。

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

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

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

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

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

我们用完全平方和减去完全平方差试试

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

等号右边化简得：

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

合并同类项得：

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

移项得：

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

交换等号两边得：

$$(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$ 要求是正整数。因为我们知道，如果平方根不是正数，只可能是 $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$，故能轻松通过此题。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	long long k;
	cin >> k;
	for (register int i = 1; i <= k; i++) {
		long long n, e, d;
		cin >> n >> e >> d;
		long long p = ((sqrt((n - e * d + 2) * (n - e * d + 2) - (n * 4))) + (n - e * d + 2)) / 2;
		long long q = (n - e * d + 2) - p;
		if (p * q == n && e * d == (p - 1) * (q - 1) + 1 && p > 0 && q > 0) {
			cout << (p < q ? p : q) << ' ' << (p > q ? p : q) << endl;
		} else {
			cout << "NO" << endl;
		}
	}
	return 0;
}