P8814 [CSP-J 2022] 解密 题解（二元一次方程）

[CSP-J 2022] 解密

题目描述

给定一个正整数 k k k，有 k k k 次询问，每次给定三个正整数 n i , e i , d i n_i, e_i, d_i ni​,ei​,di​，求两个正整数 p i , q i p_i, q_i pi​,qi​，使 n i = p i × q i n_i = p_i \times q_i ni​=pi​×qi​、 e i × d i = ( p i − 1 ) ( q i − 1 ) + 1 e_i \times d_i = (p_i - 1)(q_i - 1) + 1 ei​×di​=(pi​−1)(qi​−1)+1。

输入格式

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

接下来 k k k 行，第 i i i 行三个正整数 n i , d i , e i n_i, d_i, e_i ni​,di​,ei​。

输出格式

输出 k k k 行，每行两个正整数 p i , q i p_i, q_i pi​,qi​ 表示答案。

为使输出统一，你应当保证 p i ≤ q i p_i \leq q_i pi​≤qi​。

如果无解，请输出 NO。

样例 #1

样例输入 #1

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

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 m = n - e \times d + 2 m=n−e×d+2。

保证对于 100 % 100\% 100% 的数据， 1 ≤ k ≤ 10 5 1 \leq k \leq {10}^5 1≤k≤105，对于任意的 1 ≤ i ≤ k 1 \leq i \leq k 1≤i≤k， 1 ≤ n i ≤ 10 18 1 \leq n_i \leq {10}^{18} 1≤ni​≤1018， 1 ≤ e i × d i ≤ 10 18 1 \leq e_i \times d_i \leq {10}^{18} 1≤ei​×di​≤1018
， 1 ≤ m ≤ 10 9 1 \leq m \leq {10}^9 1≤m≤109。

想看暴力70分代码的可以看我上一篇博客(哭)

解题思路如下

题目给出条件如下：
n = q ∗ p n=q*p n=q∗p
e ∗ d = ( q − 1 ) ∗ ( p − 1 ) + 1 e*d=(q-1)*(p-1)+1 e∗d=(q−1)∗(p−1)+1
可以化简如下
e ∗ d = q ∗ p − q − p + 2 e*d=q*p-q-p+2 e∗d=q∗p−q−p+2
则可以得到
1. p + q = n + 2 − e ∗ d p+q = n+2-e*d p+q=n+2−e∗d
2. q ∗ p = n q*p=n q∗p=n

根据完全平方公式

1. ( a + b ) 2 = a 2 + 2 a b + b 2 (a+b)^2 = a^2 +2ab+ b^2 (a+b)2=a2+2ab+b2
2. ( a − b ) 2 = a 2 − 2 a b + b 2 (a-b)^2 = a^2 -2ab+b^2 (a−b)2=a2−2ab+b2

则
( p − q ) 2 = ( a + b ) 2 − 4 a b (p-q)^2=(a+b)^2 -4ab (p−q)2=(a+b)2−4ab

现在 p + q p+q p+q 和 p − q p-q p−q都知道了，就可以求出p和q
p = n + 2 − e ∗ d + ( a + b ) 2 − 4 a b 2 p=\frac{n+2-e*d +\sqrt{(a+b)^2 -4ab}}{2} p=2n+2−e∗d+(a+b)2−4ab ​​
p = n + 2 − e ∗ d ( a + b ) 2 − 4 a b 2 p=\frac{n+2-e*d \sqrt{(a+b)^2 -4ab}}{2} p=2n+2−e∗d(a+b)2−4ab ​​
但是其实q也可以如下：
q = n / p q=n/p q=n/p
然后判断一下n能不能被q整除即可。
代码如下

#include<iostream>
#include<cmath> 

using namespace std;

int main() {
	int k;
	cin >> k;

	while (k--) {
		long long p = 0, q = 0;
		long long  n = 0, e = 0, d = 0;

		cin >> n >> e >> d;

		long long total = n + 2 - e * d;


		int flag = 0;
		
		p = total + sqrt((total * total - 4 * n));
		p /= 2;

		if (n % p == 0) {//原作者这里再次判断p*q==n和e*d==(p-1)(q-1)+1,但是我认为再求pq的时候已经利用这两个条件，所以pq必然满足这俩条件，只需要判断n能否被p整除即可。
			q = n / p;
			
				flag = 1;

		}
		if (flag == 0)
			cout << "NO" << endl;
		else
		{//因为
			//$p=\frac{n+2-e*d +\sqrt{(a+b)^2 -4ab}}{2}$
//$p=\frac{n+2-e*d \sqrt{(a+b)^2 -4ab}}{2}$
//所以p一定大于q
			cout << p << " " << q << endl;
		}
	}
}

感谢原作者SkyWave
原文链接如下 https://www.luogu.com.cn/problem/solution/P8814