Harmonic Number (II)

题目

图片说明
给你上图所以函数，现在要算n<=1e9的结果，共T<=1000组

分析

我看网上好多人都做成了找规律，其实这是一个数学题，我参考了这位大佬的博客：传送门
下面开始以图例方式讲解
我们要求的结果其实就是下图中所有竖线的总长度
图片说明
然后我们知道这是一个反比例函数，其对称轴是y = x
图片说明
所以我们可以考虑只计算一半"面积"的方案。
所以我们可以将下图计算结果*2
图片说明
然后再减去下图的计算结果，个长度就是
图片说明

所以这里理解了，将很容易写出代码了

AC代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll T,N;

ll solve(ll x){
    ll len = sqrt(x),res = 0;
    for(int i = 1;i<=len;i++){
        res += x/i;
    }
    return res*2-len*len;
}
int main(){
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld",&N);
        printf("Case %d: %lld\n",++kase,solve(N));
    }
    return 0;
}