【题目描述】

给定一个正整数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;  }

(adsbygoogle = window.adsbygoogle || []).push({});