Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:我的推导过程In Reply To:我的推导过程 Posted by:stephtan at 2008-09-04 21:39:16 > 1/a = (1/b + 1/c)/ (1 - 1/(b*c)) > => bc-1 = a(b+c) > assume b=a+m and c=a+n (b and c is always bigger than a) > (a+m)(a+n)-1=a(a+m+a+n) > => a*a+a*n+a*m+m*n-1=2*a*a+m*a+n*a > => m*n=a*a+1 > and then > for(m=a;m>=1;m--) > if((a*a+1)%m==0) > break; > n=(a*a+1)/m 补充为什么m从a开始: 上面得到m*n=a*a+1之后,那我们要求的就是2*a+m+n的最小值了,化成数学式: f(m)=2*a+m+(a*a+1)/m 关于这个方程式求最小值相信大家都会 就是简单的求导得出在正实数内的最小值为m=sqrt(a*a+1),但是m要取的是整数。所以m的值可以从sqrt(a*a)开始,也就是a开始。又由于m在【1,a】是单调递减的,所以最接近a的就是答案。至于为 什么不考虑m从【a,a*a+1】,也是有原因的。实际上,算这个区间的时候也是可以得出答案的,不过 区间的长度惊人了,a=6000时是最坏情况[6000,36000001],TLE.但是,因为它的左右两边具有f(m)对称关系,所以,我们考虑小区间的[1,a],并且从大到小考虑...答案也就很快出来了。。。 顶~~楼主牛叉~~ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator