模板——补充

数论分块。

数论分块

求 \(\sum_{i=1}^n \lfloor n/i\rfloor\)，时间复杂度为 \(O(\sqrt n)\)。

long long H(int n) {
  long long res = 0;  // 储存结果
  int l = 1, r;       // 块左端点与右端点
  while (l <= n) {
    r = n / (n / l);  // 计算当前块的右端点
    // 累加这一块的贡献到结果中。乘上 1LL 防止溢出
    res += 1LL * (r - l + 1) * (n / l);
    l = r + 1;  // 左端点移到下一块
  }
  return res;
}