今天上午终于把最后一题D题水掉了。我的二分也算是ＡＫ了了吧。
这题可以说我还是有版权的，嘿嘿~~越来越有意思了！
说一下怎么做吧。
听说有公式就试着自己推了一下，感觉不错呢。
首先我们可以看出
a1=1,a2=3,a3=6. 很显而易见的an=(1+n)*n/2;
那么Sn怎么求呢？？？Sn=∑an=(1/2)∑(n*n+n)=0.5*(∑n*n+∑n);
这样就转化为连续自然数平方的和与连续自然数的和了。
连续自然数和:(1+n)*n/2
平方的和公式:n(n+1)(2n+1)/2
立方的和公式:[n(n+1)/2]^2
将公式带入最终化简------>Sn=n(n+1)(n+2)/6; 很漂亮的一个公式诞生了
接下来用二分来搜索答案就好了。
觉得自己的代码还是很美观的~虽然还有漏洞
#include<iostream>
#define MAXLayer 1111111
using namespace std;__int64 layerSum[MAXLayer];__int64 getSum( __int64 m )
{__int64 sum;sum=m*(m+1)/2;if( sum%3==0 ){sum/=3;sum*=(m+2);}else sum*=(m+2)/3;return sum;
}int BinarySeachLayer( __int64 &num )
{__int64 l=1,r=3810776,m;__int64 sum;while( m=(l+r)/2,l<r ){sum=getSum(m);if( sum>=num ) r=m;else l=m+1;}num-=getSum(m-1);return (int)m;
}int BinarySeachRow( __int64 &num )
{__int64 l=1,r=3810776,m;__int64 sum;while( m=(l+r)/2,l<r ){sum=(1+m)*m/2;if( sum>=num ) r=m;else l=m+1;}num-=(m-1)*m/2;return (int)m;
}
int main()
{__int64 N;int T;scanf( "%d",&T );while( T-- ){ scanf("%I64d",&N);int Layer=BinarySeachLayer( N );int Row=BinarySeachRow( N );int Column=N;printf( "%d %d %d\n",Layer,Row,Column );}return 0;
}