题面
思路
思路一:暴力枚举(歪解)
时间复杂度 ,所以分数拿不全, 点超时。
// Author: PanDaoxi
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k, n, e, d, p, q;
bool flag;
signed main(){
ios :: sync_with_stdio(false);
cin >> k;
while(k--){
cin >> n >> e >> d;
flag = false;
for(int i=1; i<=n; i++){
if(n % i) continue;
p = i, q = n / i;
if(e*d == n - q - p + 2){
if(p > q) swap(p, q);
cout << p << " " << q << endl;
flag = true;
break;
}
}
if(!flag) cout << "NO" << endl;
}
return 0;
}
思路二:数学(正解)
知识:
- 完全平方公式:
- 简单的应用:
// Author: PanDaoxi
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k, n, e, d, p, q, a, b;
signed main(){
ios :: sync_with_stdio(false);
cin >> k;
while(k--){
cin >> n >> e >> d;
a = n + 2 - e*d; // a = p + q
b = sqrt(a*a - 4*n); // b = p - q;
p = (a + b) / 2;
q = a - p;
if(p*q == n){ // 相乘得原数
if(p > q) swap(p, q);
cout << p << " " << q << endl;
}
else{
cout << "NO" << endl;
}
}
return 0;
}