当时该死的我只拿了60分(悲
推导与思路
先来推\(e\times d\):
\(ed=(p-1)(q-1)+1=p(q-1)-q+1+1=pq-p-q+2\)
带入\(n=pq\):
\(ed=n-p-q+2\)
再把pq移到等号左边,即可得到最终的式子:
\(p+q=n-ed+2\)
再看看数据范围,明显\(O(n^2)\)甚至\(O(n\sqrt{n})\)都不够,时间只能是\(O(n\space log\space n)\)
所以,这题的正解——二分也就很显而易见了
我们只需要枚举\(p\),再求出\(q=n-ed+2-p\),最后很具和一定差小积大的思想,即可写出代码
代码
时间有点晚借鉴了一下tj(逃
#include<bits/stdc++.h>
#define int long long
using namespace std;
void run()
{
int n,e,d,l,r,mid,f=0,p,q,t;
cin>>n>>e>>d;
l=1,r=sqrt(n),t=n-e*d+2;
while(l<=r)
{
mid=(l+r)>>1;
p=mid,q=t-mid;
if(p*q<n) l=mid+1;
else r=mid-1;
}
if(l*(t-l)==n) cout<<l<<" "<<t-l<<endl;
else cout<<"NO"<<endl;
return ;
}
signed main()
{
int t;
cin>>t;
while(t--)
{
run();
}
}