数论分块

对于常数n，使得式子$\lfloor \frac{n}{i}\rfloor=\lfloor \frac{n}{j}\rfloor$成立的最大的i<j<n的j值为$\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor}\rfloor$,即值$\lfloor \frac{n}{i}\rfloor$所在块的右端点为$\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor}\rfloor$

例题：T组数据，每组一个整数 。对于每组数据，输出$\sum_{i=1}^{n}\lfloor \frac{n}{i}\rfloor$

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

有时候需要用到特殊的转化

$a\%b=a-b*\lfloor\frac{a}{b}\rfloor$