当前位置：首页 > 题解目录 > 正文内容

【题解】解密

亿万年的星光12个月前 (10-05)题解目录20699

【题目描述】

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

【样例输入】

【样例输出】

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;
}