二分,10 Pts 求助!
查看原帖
二分,10 Pts 求助!
545986
Jerrycyx楼主2022/11/9 22:04

RT,用了二分,但是官方数据除了 #7 其它全错。

二分害死人!!!

#include<cstdio>
#include<algorithm>

#define LL long long
#define INF 0x3f3f3f3f

using namespace std;

int k;

int main()
{
//	freopen("decode.in","r",stdin);
//	freopen("decode.out","w",stdout);
	
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
	{
		LL n,d,e;
		scanf("%lld%lld%lld",&n,&d,&e);
		LL tmp=2+n-e*d;//p+q=tmp,p*q=n
		LL l=1,r=tmp;
		LL p=-INF,q=-INF;
		while(l<r)
		{
			LL mid=(l+r)>>1;
			LL pq=mid*(tmp-mid);
			if(pq==n)
			{
				p=mid,q=(tmp-mid);
				break;
			}
			if(pq<n) l=mid+1;
			else r=mid;
		}
		if(p==-INF&&q==-INF) printf("NO\n");
		else printf("%lld %lld\n",p,q);
	}
	return 0;
}
2022/11/9 22:04
加载中...