\[q_i = \frac{n_i - e_i \times d_i + 2 + \sqrt{ n_i ^ 2 + e_i ^ 2 \times d_i ^ 2 - 2 \times n_i \times e_i \times d_i - 4 \times e_i \times d_i + 4}}{2}; \]
这样的\(p_i\)和\(q_i\)就能满足\(p_i\)比\(q_i\)小了。
额，得出来的\(p_i\)和\(q_i\)若不满足题目要求就是无解的情况啦！
代码：
Link
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t;
int n;
int m;
int k;
int l;
int r;
int s;
int p;
int q;
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>t;
while(t--){
cin>>n>>m>>k;
l=n-m*k+2;
p=(l-sqrt(l*l-4*n))/2;
q=(l+sqrt(l*l-4*n))/2;
if(p*q==n||((p-1)*(q-1)+1)==m*k){
cout<<p<<" "<<q<<"\n";
}
else{
cout<<"NO\n";
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
Step3 二分：
二分解法是从暴力的思路继续向下推导的：
话说上面写到了这个式子：
\[p_i + q_i = n_i - e_i \times d_i + 2 ; \]
也就是\(p_i + q_i\)是一定的，那么根据和积原理，\(p_i + q_i\)具有单调性，所以我们就可以使用二分查找枚举\(p_i\)或\(q_i\)来寻找答案啦！
在这里，我们枚举\(p_i\)来找到答案，原因有两点：
有不会和积原理的童鞋看这：
参考网：Link
Luogu：Link
（反正我是都没看懂，比赛的时候直接用的二分，根本没考虑单调性，但是还是过了
代码：
Link
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k;
int n;
int e;
int d;
int h;
int x;
int sx;
int ef(int l, int r, int n, int m){
while(l<=r){
int mid=((l+r)>>1);
int j=mid*(m-mid);
if(j==n){
return mid;
}
else{
if(j<n){
l=mid+1;
}
else{
r=mid-1;
}
}
}
return -114514;
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>k;
while(k--){
cin>>n>>e>>d;
h=n-e*d+2;
sx=ceil(h/2);
x=ef(1ll,sx,n,h);
if(x!=-114514){
cout<<x<<" "<<h-x<<"\n";
}
else{
cout<<"NO\n";
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
完结撒花！