Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:我的推导过程

Posted by 200831000423 at 2010-04-30 13:22:03 on Problem 1183 and last updated at 2010-04-30 13:23:29
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator