[BZOJ2048] [2009国家集训队] 书堆

Description

Input

　　第一行正整数 N M

Output

　　一行（有换行符），L，表示水平延伸最远的整数距离 (不大于答案的最大整数)

Sample Input

#1
1 100

#2
2 100

Sample Output

HINT

　　N <= 10^18

　　数据保证答案 < 10^6

Source

　　By 何朴藩

Solution

　　好~~~严谨的物理题。画一下图就会发现最上面的书可以露出1/2（指相对它下面的那本书，下同），第二本书可以露出1/3，第三本书可以露出1/4，等等。

 1 #include <cmath>
 2 #include <iostream>
 3 using namespace std;
 4 int main()
 5 {
 6     long long n, m;
 7     double ans = 0;
 8     cin >> n >> m;
 9     if(n <= 200000LL)
10         for(long long i = 1; i <= n; i++)
11             ans += 1.0 * m / (i * 2);
12     else
13         ans = m * (log(1.0 * n + 1) + 0.5772156649015329) / 2;
14     cout << (int)ceil(ans) - 1 << endl;
15     return 0;
16 }

View Code