100
#LS1261. 【提高】数论分块

【提高】数论分块

【模板】数论分块

给定正整数 nn,求

∑i=1n⌊ni⌋\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor

其中 ⌊ni⌋\lfloor\frac{n}{i}\rfloor 表示求不超过 ni\frac{n}{i} 的最大整数,比如:⌊52⌋=2\lfloor\frac{5}{2}\rfloor=2,⌊103⌋=3\lfloor\frac{10}{3}\rfloor=3

可以理解为就是 C++ 中的除法

输入格式

第 1 行包含 1 个正整数 TT;

接下来 TT 行,每行包含一个正整数 n(1≤n≤1012)n(1 \le n \le 10^{12})

输出格式

对于每组数据输出 1 行表示答案

2
5
10
10
27

提示

【样例 #1 解释】

  • $\lfloor\frac{5}{1}\rfloor+\lfloor\frac{5}{2}\rfloor+\lfloor\frac{5}{3}\rfloor+\lfloor\frac{5}{4}\rfloor+\lfloor\frac{5}{5}\rfloor=5+2+1+1+1=10$
  • 数论分块
  • oiwiki: 数论分块
  • 学习总结-莫比乌斯反演
  • 考虑 n=10n = 10 时的结果,10+5+3+2+2+1+1+1+1+1=2710+5+3+2+2+1+1+1+1+1=27
  • 可以发现 ⌊106⌋\lfloor\frac{10}{6}\rfloor 到 ⌊1010⌋\lfloor\frac{10}{10}\rfloor 的结果都是 11
  • 设 k=⌊nl⌋k = \lfloor\frac{n}{l}\rfloor,rr 是使得 ⌊nx⌋=k\lfloor\frac{n}{x}\rfloor=k 的最大的 xx(比如 n=10,l=6,r=10n=10, l=6, r = 10)
  • 由 ⌊nx⌋=k\lfloor\frac{n}{x}\rfloor=k 得到 n=xk+rn=xk+r,当 r=0r=0 时,xx 最大是 ⌊nk⌋\lfloor\frac{n}{k}\rfloor
  • 所以 $r=\lfloor\frac{n}{k}\rfloor=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$
  • 所以我们可以这样计算
i64 T, n;
cin >> T;
while (T--) {
    cin >> n;
    i64 ans = 0;
    for (i64 l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans += n / l * (r - l + 1);
    }
    cout << ans << '\n';
}
  • 可以证明 ⌊ni⌋\lfloor\frac{n}{i}\rfloor 最多有不超过 ⌊2n⌋\lfloor 2\sqrt n \rfloor 个值
    • 当 i≤⌊n⌋i \le \lfloor \sqrt n \rfloor 时,⌊ni⌋\lfloor\frac{n}{i}\rfloor 最多有 ⌊n⌋\lfloor \sqrt n \rfloor 个不同的值
    • 当 i>⌊n⌋i > \lfloor \sqrt n \rfloor 时,⌊ni⌋≤n\lfloor\frac{n}{i}\rfloor \le \sqrt n,也只有 ⌊n⌋\lfloor \sqrt n \rfloor 个不同的值
  • 所以计算 ∑i=1n⌊ni⌋\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor 的时间复杂度是 O(n)O(\sqrt n)
请思考后再点击查看提示

数据规模与限制

  • 1≤T≤101 \leq T \leq 10
  • 1≤n≤10121 \leq n \leq 10^{12}

来源