LightOJ 1245 Harmonic Number调和数

Description

计算

画图，画出函数图像：y = n/x，以 y = x对称(以n == 5为例)

可以用 横坐标表示i 从该点画一条垂直的线

这条线上的所有整数点的个数就是 n / i

那么n / 1 + n / 2 + n / 3 + …… n / (n-2) + n / (n-1) + n / n

可以表示为方程的曲线与坐标轴围成的面积内的整数点的个数

对称，求左边梯形内点数，乘2减去重叠的那部分

部分原文链接：https://blog.csdn.net/weixin_43237242/article/details/88780203

Code

int main()
{
    int t, n, cnt = 1;;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        ll ans = 0;
        int tem = sqrt(n);
        for(int i = 1; i <= tem; ++i)
            ans += n / i;
        ans <<= 1;
        ans -= tem * tem;
        printf("Case %d: %lld\n", cnt++, ans);
    }
    return 0;
}