【寒假每日一题】AcWing 4729. 解密（补）

一、题目

1、原题链接

4729. 解密

2、题目描述

给定一个正整数 k有 k次询问每次给定三个正整数 ni,ei,di求两个正整数 pi,qi使 $ni=pi\times qi$$ei\times di=(pi-1)(qi-1)+1$。
输入格式
第一行一个正整数 k表示有 k次询问。
接下来 k行第 i 行三个正整数 ni,di,ei。
输出格式
输出 k
行每行两个正整数 pi,qi
表示答案。
为使输出统一你应当 保证 pi≤qi。
如果无解请输出 NO。
数据范围
以下记 m=n−e×d+2。
保证对于 100% 的数据1≤k≤10⁵对于任意的 1≤i≤k1≤ni≤10¹⁸1≤ei×di≤10¹⁸1≤m≤10⁹。

输入样例

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

二、解题报告

思路来源AcWing 4729. 解密寒假每日一题2023
y总yyds

1、思路分析

1)通过题目 $ni=pi\times qi$ $ei\times di=(pi-1)(qi-1)+1$两个公式化简可以推出$pi+qi=n-ei\ast di+2$而题目给出了$m=n-e\times d+2$。所以我们可以有 $m=pi+qi$通过高亮表示的两式不难联想到韦达定理及其逆定理我们可以根据上述两式来构造一个一元二次方程二元方程的解就是对应的pi和qi。
2模拟上述过程输出相应结果即为所求。

2、时间复杂度

时间复杂度为O(n)

3、代码详解

#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=100010;
LL n[N],e[N],d[N],p,q;
int main()
{   int k;
    cin>>k;
    for(int i=0;i<k;i++){
    	cin>>n[i]>>e[i]>>d[i];
	}
	for(int i=0;i<k;i++){
		LL m=n[i]-e[i]*d[i]+2;
		LL d=m*m-4*n[i];
		LL gd=sqrt(d); 
		//判别式大于等于0才有解 
		if(d>=0){
		   //判断解是否为整数
		   /*首先根号△得为整数其次最终结果得为整数
		     分子为偶数才能确保最终结果为整数此处注意
			 运算符的优先级!高于算术运算符。根据两个分
			 子奇偶性相同也可简化代码*/ 
		   if(gd*gd==d&&!((m-gd)%2)&&!((m+gd)%2))
			 cout<<(m-gd)/2<<" "<<(m+gd)/2<<endl;
		   else{
		   	  cout<<"NO"<<endl; 
		   }
		} 
		else{
			cout<<"NO"<<endl; 
		}
	}
    return 0;
}

三、知识风暴

韦达定理及其逆定理

韦达定理
针对一个一元二次方程 a²x+bx+c=0a不为0且a,b,c均为实数且存在根则有 x1+x2=-b/a, x1*x2=c/a。
逆定理
如果存在 x1+x2=-b/a, x1*x2=c/a可据此构造一个一元二次方程使得该方程的解为 x1,x2。