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 |
我向一位大牛请教的,分享一下!高精度 命题是:按照题目的要求 取 a1=2 a2=3 ... an=a1*a2*..*a(n-1)+1 的时候,剩下最少,为1/(a1*a2*...*an),令r(n)=a1*a2*...an 然后归纳的时候 利用下面这个性质 k+1时候,前k个取完后剩下越少,取完第k+1个之后,剩下也越少 这个可以用函数单调性比较简单证明 假设取完前k个剩余1/c (由于前k的取法随意,c不一定是整数) 取第k+1个的时候,取1/([c]+1)使得剩余最少,而这个值是f(c)=1/c-1/([c]+1) 容易证明f单调减,而由归纳假设,c的最大值是r(k),所以当c取r(k)的时候 k+1步取完剩余最少 计算一下a[k+1]和剩余,容易发现得证 完善一下就比较严格了。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator