O(1)算法,求Hack
查看原帖
O(1)算法,求Hack
385733
THE_ERA楼主2022/10/29 20:45

已知

n=pqn=pq ed=(p1)(q1)+1ed=(p-1)(q-1)+1

则可得:

ed=pq(p+q)+2ed=pq-(p+q)+2 ned=(p+q)2n-ed=(p+q)-2 ned+2=p+qn-ed+2=p+q

则已知pq,p+q,求pq 直接套用 完全平方公式

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
long long n,d,e;
int t;       
int main(){
      //freopen("decode.in","r",stdin);
      //freopen("decode.out","w",stdout);
      scanf("%d",&t);
      while(t--){
      	scanf("%lld %lld %lld",&n,&d,&e);
      	ll k=n-e*d+2,l=k*k;
      	l-=4*n;
      	ll ch=sqrt(l);
      	if(ch*ch!=l){
      		puts("NO");
      		continue;
      	}
      	else{
      		ll l=(k+ch)/2,r=(k-ch)/2;
      		if(l>r) swap(l,r);
      		printf("%lld %lld\n",l,r);
      	}
      } 
return 0;
}

2022/10/29 20:45
加载中...