codeforces round 1093 C题解

题目描述

text

题解

已知$p$根I和$n$根L的棍子总量是$p+2 \times q$,而我们经过推算可以知道若组成n行m列的网格需要的棍子总量是$(m+1)n+(n+1)m2mn$
那么，针对$S=(m+1)n+(n+1)m2mn+m+n$，我们需要进行以下构造
$2*S+1$
经过如上构造，上述式子变成 $4mn+2m+2n+1==(2m+1)(2n+1)$,之后通过开方确定m与n的上下限，然后判断L型棍子的数量是否足够构成我们确定的$n$与$m$的值所需要的拐点,输出即可
时间复杂度为$O(√(p+2q))$,这是可以接受的

代码

void solveC()
{long long p,q;cin>>p>>q;long long ans=p+2*q;//原来的需要的棍子数量是2mn+m+n==(m+1)*n+m*(n+1)//我们需要进行构造long long handle=2*ans+1;//进行如下构造使得式子变成4mn+2m+2n+1，因式分解后==>(2m+1)(2n+1)long long pp=round(sqrt(handle));while((pp+1)*(pp+1)<=handle){pp++;}while(pp*pp>handle){pp--;}//什么二分，分明是确定二分起点for(long long i=pp;i>=1;i--){if(handle%i==0){long long b=handle/i;ll A=(i-1)/2;ll B=(b-1)/2;if(A>0&&B>0){ll min1=min(A*(B+1),B*(A+1));if(min1>=q){cout<<A<<' '<<B<<endl;return;}}}}cout<<-1<<endl;
}

这是本蒟蒻的第一篇题解，若有疏漏还请指正，谢谢喵