T2 解密
题目描述
给定一个正整数 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。
| 测试点编号 | k≤ | n≤ | m≤ | 特殊性质 |
|---|---|---|---|---|
| 1 | 10^3 | 10^3 | 10^3 | 保证有解 |
| 2 | 10^3 | 10^3 | 10^3 | 无 |
| 3 | 10^3 | 10^9 | 6×10^4 | 保证有解 |
| 4 | 10^3 | 10^9 | 6×10^4 | 无 |
| 5 | 10^3 | 10^9 | 10^9 | 保证有解 |
| 6 | 10^3 | 10^9 | 10^9 | 无 |
| 7 | 10^5 | 10^18 | 10^9 | 保证若有解则 p=q |
| 8 | 10^5 | 10^18 | 10^9 | 保证有解 |
| 9 | 10^5 | 10^18 | 10^9 | 无 |
| 10 | 10^5 | 10^18 | 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分