4137: 解密 [CSP-J 2022]
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：48
解决：3
题目描述
给定一个正整数 ，有 次询问，每次给定三个正整数 ，求两个正整数 ，使 、。
输入
第一行一个正整数 ，表示有 次询问。
接下来 行，第 行三个正整数 。
输出
输出 行，每行两个正整数 表示答案。
为使输出统一，你应当保证 。
如果无解，请输出 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提示
【数据范围】
以下记 。
保证对于 的数据，，对于任意的 ，， ，。
#include<bits/stdc++.h>
using namespace std;
/*方法一：枚举法-时间复杂度-O(k*sqrt(n))*/
int main(){
int k;cin>>k;
long long n,d,e,q;
while(k--) {
scanf("%ld%ld%ld",&n,&d,&e);
bool flag=false;
for(long long p=1;p*p<=n;p++) {
if(n%p==0) {
q=n/p;
if(e*d==(p-1)*(q-1)+1) {
flag=true;
cout<<p<<" "<<q<<endl;
break;
}
}
}
if(!flag) cout<<"NO"<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
/*方法二：数学求根法-时间复杂度-O(k)*/
/*
n=p*q
e*d=(p-1)*(q-1)+1
e*d=pq-p-q+2
p+q=n-e*d+2=m
n-e*d+2=m
p+q=m
p+n/p=m
p^2-mp+n=0
*/
int main(){
int k;cin>>k;
long long n,d,e,q;
while(k--) {
cin>>n>>d>>e;
long long m=n-e*d+2;
long long delta=m*m-4*n;
//无解
if(delta<0) cout<<"NO"<<endl;
//没有整数解
else if(sqrt(delta)!=int(sqrt(delta)))
cout<<"NO"<<endl;
//没有整数解
else if((m-int(sqrt(delta)))%2!=0)
cout<<"NO"<<endl;
else {
cout<<(m-int(sqrt(delta)))/2<<" "<<(m+int(sqrt(delta)))/2<<endl;
}
}
return 0;
}