P8814 [CSP-J 2022] 解密 题解

解方程

$题目中说，n = pq，ed = (p-1)(q-1)+1，m=n-ed+2.$

$把ed的式子展开，得到:$

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

$ed=pq-p-q+2$

$再把展开后的式子带入m中，得:$

$m=n-(pq-p-q+2)+2.$

$m=n-pq+p+q-2+2$

$\because n=pq$

$\therefore m=pq-pq+p+q-2+2$

$m=p+q.$

$如果想要求出p和q的值，那么可以再构造出一个二元一次方程,然后构成$

$一个二元一次方$组

$所以，最简单的方法就是求出p-q的值$

p - q = ?

$回想起完全平方公式$

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

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

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

$刚好，如果p=a,q=b呢？$

$(p-q)^2=(p+q)2-4pq$

$左右开方$

$p-q=\sqrt {(p+q)^2-4pq}.$

$\because p+q=m=n-ed+2，n=pq$

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

方程组

$\left{\begin{matrix}
p+q=n-ed+2&\
p-q=\sqrt{(n-ed+2)^2-4n} &
\end{matrix}\right.$

$输入n,e,d三个数后，就可以求出p-q和p+q的值了.$

$然后用加减消元法.$

$两式相加，得:$

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

$两式相减，得:$

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

判断是否是正解

$前2个条件直接套就行，也就是pq=n,ed=(p-1)(q-1)+1.$

$因为在开根的时候，可能会产生一些不是正解的数，所以只要判断p，q是否$

$为真即可.$

代码

#include<bits/stdc++.h>
using namespace std;
int k;
int main() {
//	freopen("decode.in", "r", stdin);
//	freopen("decode.out", "w", stdout);
	scanf("%d", &k);
	while (k--) {
		long long n, d, e;
		scanf("%lld%lld%lld", &n, &d, &e);
		// 接下来就是套公式 
		long long p = (n - e * d + 2 + sqrt((n - e * d + 2) * (n - e * d + 2) - 4 * n)) / 2;
		long long q = (n - e * d + 2 - sqrt((n - e * d + 2) * (n - e * d + 2) - 4 * n)) / 2;
		// 判断这2个解是否成立 
		if (p * q == n && e * d == (p - 1)  * (q - 1) + 1&& p && q) {
			if (p > q) swap(p, q); // 小的数在前面 
			printf("%lld %lld\n", p, q);
		}
		else
			printf("NO\n");
	}
	return 0;
}

知识点

$完全平方公式，方程$