题目描述
给定一个正整数 \(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 \leq 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 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 \times d + 2\)。
保证对于 \(100\%\) 的数据,\(1 \leq k \leq {10}^5\),对于任意的 \(1 \leq i \leq k\),\(1 \leq n_i \leq {10}^{18}\),\(1 \leq e_i \times d_i \leq {10}^{18}\)
,\(1 \leq m \leq {10}^9\)。
测试点编号 | \(k \leq\) | \(n \leq\) | \(m \leq\) | 特殊性质 |
---|---|---|---|---|
\(1\) | \(10^3\) | \(10^3\) | \(10^3\) | 保证有解 |
\(2\) | \(10^3\) | \(10^3\) | \(10^3\) | 无 |
\(3\) | \(10^3\) | \(10^9\) | \(6\times 10^4\) | 保证有解 |
\(4\) | \(10^3\) | \(10^9\) | \(6\times 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\) | 无 |
附件下载
解题思路
看到这道题给出了这么多变量,怎么越看越像一道可以用数学来解决的题目?
虽然二分确实可以通过在区间内找然后看答案是否合法,但是对于我这种二分容易写错的蒟蒻一般不敢上来就写二分,数学方法一下子秒算出来的感觉不香吗?
因此,我们就直接根据题目给的变量来列方程。
方程解出来了之后,这代码不就也很简单成了吗?(和T1的码量差不多)
完整代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k, n, e, d;
int p, q, a, b;
int read() {
int x = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * w;
}
signed main() {
k = read();
while (k--) {
n = read(); e = read(); d = read();
a = n - e * d + 2;
b = sqrt(a * a - 4 * n);
p = (a + b) / 2;
q = a - p;
if (p * q == n) {
if (p > q)
swap(p, q);
cout << p << " " << q << endl;
}
else cout << "NO" << endl;
}
return 0;
}
给个赞吧!
标签:10,ch,样例,T2,decode,leq,2022,18,CSP From: https://www.cnblogs.com/GTGumiiL/p/17108399.html