题目描述
给定一个正整数 \(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。
样例
样例输入
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
样例输出
2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
思路
数据范围
| 测试点编号 | \(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\) | 无 |
由数据范围可知，要开long long.
由题目给出的代数式手动解，你会看到惊喜：
\[p+q=n-ed+2
\]
在题目的数据范围标题下，你会看见：
\[m=n-e\times d+2
\]
这恰好说明，我们手动解代数式的思路是对的。
初一学生看到这里应该会异常兴奋，因为在初一就学过了一元二次方程，其中告诉我们要解出\(p,q\)的值，就要算出\(p+q\)和\(p-q\)的值。而我们现在已知\(p+q=n-ed+2,pq=n\)，通过完全平方公式，就可以得到\(p-q\)了。
解题过程略(真的太长了)。
综上所述，我们可以解出：
\[p=(m+sqrt(m^2+4n))/2
\]
\[q=(m-sqrt(m^2+4n))/2
\]
其中，\(m=n-ed+2\).
但是，为了防止喜提WA，我们还需要进行特判。
这道题只要掌握了思路，代码还是很好写的。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
long long n,e,d;
cin>>n>>e>>d;
long long m=n-e*d+2;
long long p,q;
p=(m+sqrt(m*m-4*n))/2;
q=(m-sqrt(m*m-4*n))/2;
if(n==p*q&&e*d==p*q-q-p+2&&p!=0&&q!=0){
cout<<min(p,q)<<" "<<max(p,q)<<endl;
}
else{
cout<<"NO"<<endl;
}
}
return 0;
}