【题解】解密
【题目描述】
给定一个正整数k,有k次询问，每次给定三个正整数ni,ei,di,求两个正整数pi,qi。
使ni=pi * qi, ei * di =(pi -1) *(qi-1) + 1
【输入描述】
第一行一个正整数k,表示有k次询问。
接下来k行，第i行三个正整数ni,di,ei。
【输出描述】
输出k行，每行两个正整数pi,qi表示答案。
为使输出统一，你应保证pi<=qi。
如果无解，请输出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
【数据范围】
m=n-e*d +2
保证对于100的数据，1<=k<=10^5，对于任意的1<=i<=k,1<=ni<=10^18,
1<=ei*di<=10^18, 1<=m<=10^9
【题目分析】
上面的公式可以转换成下面这样：
题目读入是n、e、d这三个数求解的是p和q。两个未知数，两个方程。类似一元二次方程。
题目的数据范围最大是10^18，在long long 附近，如果我们用模拟法的话，应该开long long，不然数据会爆掉。
【参考答案一】：模拟法。
#include<bits/stdc++.h>
using namespace std;
long long n,e,d; //三个数
int k; //k次询问
int main(){
scanf("%d",&k);
while(k--){
int flag =1; //表示有没有找到一个解
scanf("%lld%lld%lld",&n,&e,&d);
//枚举p
for(long long p=1;p<=n;p++){
if(n%p!=0){
continue; //跳过不符合第一个式子的
}
long long q= n/p; //得出q
//根据题目要求枚举两个式子
if( (e*d == (p-1)*(q-1)+1) &&(n==p*q) ){
flag=0;
cout<<min(p,q)<<" "<<max(p,q)<<endl;
break;
}
}
if(flag==1){
cout<<"NO"<<endl;
}
}
return 0;
}上面这个代码完全依靠模拟的方式进行求解，20个测试点可以对8个点，也就是40分。上面的代码有一处可以改进的地方，就是 p<=n，这一处改成p*p<=n，这样可以缩减运算范围。改了这一处以后，对了12个点也就是60分，其余的点全部超时，不能得满分。需要考虑其他方案
【参考答案二】：化简后利用性质解方程
题目中有个提示 m=n-e*d+2，我们把式子化简一下。
那么得出一个结论n=p*q , m=p+q。 这是韦达定理。
根据韦达定理，c=n , -b = m， a=1, （n,m是输入的已知量）把这个结论代入到上述式子中。
#include<bits/stdc++.h>
using namespace std;
long long n,e,d; //三个数
int k; //k次询问
int main() {
scanf("%d",&k);
while(k--) {
scanf("%lld%lld%lld",&n,&e,&d);
long long m=n-e*d+2;
long long dd =m*m-4*n; //b^2-4ac
if(dd<0) {
cout<<"NO"<<endl; //一元二次方程无解情况
} else {
//解方程
long long p= ((m*1.0)-sqrt(dd))/2*1.0;
long long q= ((m*1.0)+sqrt(dd))/2*1.0;
//上面的计算因为精度问题需要再次判断
if(p>0 && q>0 && p*q==n && p+q==m ){
cout<<p<<" "<<q<<endl;
}else{
cout<<"NO"<<endl;
}
}
}
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。