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

用了恒等式……

Posted by MIRKING at 2008-06-30 22:15:20 on Problem 2000 and last updated at 2008-06-30 22:23:44
In Reply To:有哪位大牛行行好告诉我公式是怎么推导出来的吧? Posted by:chqch172443 at 2008-06-30 16:27:41
用d表示日期,c表示该天所得到的coin数,列出它们的对应关系:

d:1,2,3,4,5,6,7,8………………p,     q,……
c:1,2,2,3,3,3,4,4…n(j)…n(n),n+1(1),…
其中n(j)表示数字n的第j次出现
则n(n)对应的就是p=n*(n+1)/2

根据恒等式:
(2n+1)^2≡8*(n*(n+1)/2)+1
由p=n*(n+1)/2等价变化
(2n+1)^2≡8*p+1
变形就得到
n=(sqrt(8*p+1)-1)/2
也就是说,只要给出了p就知道了n
但这仅仅是在n(n)时也就是p=n*(n+1)/2时的特殊情况,下面推导一般情况:
令f(p)=(sqrt(8*p+1)-1)/2,则f(p)为严格单调递增函数,则必有:
若:p1=i*(i+1)/2<p2<=p3=(i+1)*(i+2)/2
则:f(p1)=i<f(p2)<=f(p3)=i+1
由于p2对应的d必然是整数,所以p2对应的是i+1
综上所述:n=ceil((sqrt(8*p+1)-1)/2)

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