本文共 1027 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要计算给定整数n的调和数的和，即H(n) = n/1 + n/2 + ... + n/n，其中每个项都是向下取整的。直接使用简单的循环方法在n很大时效率很低，因此我们需要一种更高效的方法。

方法思路

我们可以利用数学性质来优化计算。具体来说，当i小于等于sqrt(n)时，直接计算n/i；而当i大于sqrt(n)时，利用k = n/i，其中k的范围是1到sqrt(n)。这种方法可以将计算复杂度从O(n)减少到O(sqrt(n))，大大提高效率。

解决代码

#include 
   
    
#include 
    
     
using namespace std;
long long H(int n) {
    long long sum = 0;
    int j = sqrt(n);
    for (int i = 1; i <= j; ++i) {
        sum += n / i;
    }
    for (int k = 1; k <= j; ++k) {
        int lower = n / (k + 1) + 1;
        int upper = n / k;
        if (upper < lower) continue;
        sum += k * (upper - lower + 1);
    }
    return sum;
}
int main() {
    int t;
    cin >> t;
    for (int cas = 1; cas <= t; ++cas) {
        int n;
        cin >> n;
        long long res = H(n);
        printf("Case %d: %lld\n", cas, res);
    }
    return 0;
}
    
   

代码解释

这种方法通过将问题分成两部分，利用数学性质优化了计算过程，有效地将复杂度从O(n)减少到O(sqrt(n))，从而提高了效率。