Luogu

分析

首先通过画图找规律可以得到答案为

$$ m\sum_{i=1}^n\frac{1}{2i} $$

它等于

$$ \frac{m\sum_{i=1}^n\frac{1}{i}}{2} $$

于是只要考虑如何计算 $\sum\limits_{i=1}^n\frac{1}{i}$ 即可。

通过各种方法可以发现

$$ \left(\sum_{i=1}^n\frac{1}{i}\right)-\ln n $$

收敛于欧拉-马歇罗尼常数,这个常数的值约为 $0.5772156649$ 。

于是当 $n$ 比较小时,暴力计算;当 $n$ 比较大时,$\sum\limits_{i=1}^n\frac{1}{i}$ 约等于 $\ln n+0.5772156649$ 。

根据题意,算出答案后要减掉一个 $\epsilon$ 再取下整。这个 $\epsilon$ 取 $10^{-12}$ 就差不多了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

const long double eps=1e-12;

int main() {
    ll n,m; scanf("%lld%lld",&n,&m);
    long double ans=0;
    if (n<=10000000)
        for (re int i=1;i<=n;++i) ans+=1.0/i;
    else
        ans=log(n)+0.5772156649;
    ans=ans*m/2-eps;
    printf("%d\n",(int)(floor(ans)+0.5));
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 45 PM