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 |
用了恒等式……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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator