一、题目
1、原题链接
4729. 解密
2、题目描述
给定一个正整数 k，有 k次询问，每次给定三个正整数 ni,ei,di，求两个正整数 pi,qi，使 n i = p i × q i ni=pi×qini=pi×qi，e i × d i = ( p i − 1 ) ( q i − 1 ) + 1 ei×di=(pi−1)(qi−1)+1ei×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≤105，对于任意的 1≤i≤k，1≤ni≤1018，1≤ei×di≤1018，1≤m≤109。
输入样例：
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)通过题目 n i = p i × q i ni=pi×qini=pi×qi ，e i × d i = ( p i − 1 ) ( q i − 1 ) + 1 ei×di=(pi−1)(qi−1)+1ei×di=(pi−1)(qi−1)+1，两个公式化简可以推出p i + q i = n − e i ∗ d i + 2 pi+qi=n-ei*di + 2pi+qi=n−ei∗di+2，而题目给出了m = n − e × d + 2 m=n−e×d+2m=n−e×d+2。所以我们可以有 m = p i + q i m=pi+qim=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;
}
三、知识风暴
韦达定理及其逆定理
韦达定理：
针对一个一元二次方程 a2x+bx+c=0，a不为0，且a,b,c均为实数，且存在根，则有 x1+x2=-b/a, x1*x2=c/a。
逆定理：
如果存在 x1+x2=-b/a, x1*x2=c/a，可据此构造一个一元二次方程使得该方程的解为 x1,x2。
