P8814 [CSP-J 2022] 解密（民间数据）题解

题目

链接

https://www.luogu.com.cn/problem/P8814?contestId=90215

字面描述

题目描述

给定一个正整数 $k$，有 $k$ 次询问，每次给定三个正整数 $n_i,e_i,d_i$，求两个正整数 $p_i,q_i$，使 $n_i=p_i\times q_i$、$e_i\times d_i=(p_i-1)(q_i-1)+1$。

输入格式

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

接下来 $k$ 行，第 $i$ 行三个正整数 $n_i,d_i,e_i$。

输出格式

输出 $k$ 行，每行两个正整数 $p_i,q_i$ 表示答案。

为使输出统一，你应当保证 $p_i\le q_i$。

如果无解，请输出 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
3
4
5
6
7
8
9
10
11

样例输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
1
2
3
4
5
6
7
8
9
10

提示

【样例 #2】

见附件中的 decode/decode2.in 与 decode/decode2.ans。

【样例 #3】

见附件中的 decode/decode3.in 与 decode/decode3.ans。

【样例 #4】

见附件中的 decode/decode4.in 与 decode/decode4.ans。

【数据范围】

以下记 $m=n-e\times d+2$。

保证对于 $100\%$ 的数据，$1\le k\le {10}^5$，对于任意的 $1\le i\le k$，$1\le n_i\le {10}^{18}$，$1\le e_i\times d_i\le {10}^{18}$
，$1\le m\le {10}^9$。

思路分析

数据分析

题目中的,n,e,d均已给出。求p,q
大概关系如下：
n=pq;
ed=(p-1)(q-1)+1;
=pq-p-q+2
题目中给了一个m 值的定义
m=n-ed+2; 代入n,ed;
m=pq-pq+p+q-2+2
=p+q;
若把所有已经知道的罗列起来,条件如下：
n-ed+2=p+q;
n =pq;
根据这2个关系式，是可以看出p,q取值的唯一性。

那么只要知道p的值，q的值一定确定.

方法

接下来面临的问题是如何确定p的值

枚举

1. m的最大取值范围是1e9 枚举 时间复杂度 O(km) TLE

2. 从n入手
   像分解因数一样 枚举范围是sqrt(n) -> 时间复杂度 O(k* sqrt(n)） 大大的TLE！

以上两种方法写对的得分都是60分；

二分

接下来是不是没有想法了
别急
$最重要的思路就是二分p，上限1e9;$
$单次二分时间复杂度O(log(m))60$
总体时间复杂度 O(k*log(m))~6e6

时间复杂度过的去。
接下来的问题是，此解空间是否有单调有序性。

n == pq 返回pq的值
n>pq，n 当p大的时候，q小
q小的时候，p大
这对标了小学时的和同近积大
$\therefore 这个解空间不具有单调有序性，但这个解空间具有单调对称性,所以n>pq可以往任意方向二分搜索，n<pq往反方向二分即可。$
思路说的差不多了，上代码

代码实现

#include
#define ll long long
using namespace std;

int k;
ll n,e,d,ans;
int main(){
	freopen("decode.in","r",stdin);
	freopen("decode.out","w",stdout);
	scanf("%d",&k);
	while(k--){
		scanf("%lld%lld%lld",&n,&e,&d);
		e=(ll)e*d;
		ll m=n-e;
		ll l=1,r=m+1;
		ans=0;
		while(l<=r){
			ll mid=(l+r)>>1;
			ll c=m-mid+2;
			ll cnt=(ll)c*mid;
			if(cnt>n)r=mid-1;
			else if(cnt<n)l=mid+1;
			else {
				ans=mid;
				break;
			}
		}
		ll cc=m-ans+2;
		if(ans*cc!=n)printf("NO\n");
		else printf("%lld %lld\n",min(ans,cc),max(ans,cc));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33