T2 解密

[CSP-J 2022] 解密 – 洛谷

题目描述

给定一个正整数 k，有 k 次询问，每次给定三个正整数 n_i, e_i, d_i，求两个正整数 p_i, q_i，使 n_i​=p_i​×q_i​、e_i​×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​≤q_i​。

如果无解，请输出

NO

。

输入输出样例

输入 #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

说明/提示

【数据范围】

以下记 m=n−e×d+2。

保证对于 100% 的数据，1≤k≤105，对于任意的 1 ≤ i ≤ k，1 ≤ n_i ​≤10^18,1 ≤ e_i​ × d_i​ ≤ 10^18 ，1 ≤ m ≤ 10^9。

思路：for循环暴力枚举

读完题目后很容易想到将p和q全部枚举一遍得出答案，见下段代码

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

int k, n, e, d;

int main(){
	scanf("%d", &k);
	for (int i = 1; i <= k; i++){
		bool flag = true;
		scanf("%d%d%d", &n, &d, &e);
		for (int p = 1; p <= sqrt(n); p++){
			if (n % p != 0) continue;
			int q = n / p;
			if ((p - 1) * (q - 1) + 1 != e * d) continue;
			printf("%d %d\n", p, q);
			flag = false;
			break;
		}
		if (flag) printf("NO\n");
	}
	return 0;
}

这种做法没有问题，但O(n * n)的时间复杂度只能的60分

思路2：2分求解

将 e*d = (p-1)*(q-1)化简得n = p * q && m = p + q;

我们又知道：当两数和固定时，两数越接近积越大

即当p<=m/2&&q >= m/2时，p越大p*q越大。

根据p*q与n的大小关系缩小区间

于是有了以下算法

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

long long k, n, e, d, m;

int main(){
	scanf("%lld", &k);
	for (int i = 1; i <= k; i++){
		scanf("%lld%lld%lld", &n, &d, &e);
		m = n - e * d + 2;
		long long l = 0, r = m / 2 + 1, mid;
		while (l + 1 < r){
			mid = (l + r) / 2;
			if (mid * (m - mid) <= n)
				l = mid; //乘积小于n，将左边界改为mid（扩大p）
			else
				r = mid; //反之将右边界改为mid 
		}
		if (l * (m - l) == n) //如果积正好为n就输出
			printf("%lld %lld\n", l, n / l);
		else
			printf("NO\n"); 
	}
	return 0;
}

时间复杂度O(k * m) 实测100分