题目描述
给定一个正整数 \(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;
}