这道题要先求第n项在第几层,题解区求这步大多一层层枚举,好点的用二分。但是这步可以用O(1)时间求出,例如这篇题解。
我还有个想法,x(x+1)=x2x^2x2,而
(x+0.5)2(x+0.5)^2(x+0.5)2= x2+x+0.25x^2+x+0.25x2+x+0.25,
误差很小,只有0.25,大概可忽略不计,所以 x≈(2n)−0.5x\approx \sqrt(2n)-0.5x≈(2n)−0.5,也过了这道题,记录点这
但毕竟还有0.25误差,我不确定数据大了能不能过