约数

约数个数和定理

我们记 $d(i)$ 为 数 $i$ 的约数个数,存在等式

$$\sum _{i=1}^{n}d(i)=\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor$$

这个等式的证明如下

记二重计数集合 $S=\{(a,b)\in \mathbb{Z}{}_{\ge 1}^2:ab\le n\}$
含义为两个大于1的正整数$a,b$其乘积小于等于$n$我们需要得知的即为$|S|$

按积分组角度
对于每一个$i\in [1,n]$,将所有满足 $ab=i$的有序对计入$S$,这个有序对个数正好就是$d(i)$,将$i=1$到$n$累加有:

$$|S|=\sum _{i=1}^{n}d(i)\text{\hspace{1em}(1)}$$

按固定的$a$ 角度
固定$a\in [1,n]$,则满足条件的$b$的个数是满足 $ab\le n$的个数,即:

$$\{b|b\ge 1\text{ and }b\le \frac{n}{a}\}=\lfloor \frac{n}{a}\rfloor$$

累加有:

$$|S|=\sum _{a=1}^n\lfloor \frac{n}{a}\rfloor \text{\hspace{1em}(2)}$$

而这两个计数的是同一个集合,结合$(1),(2)$可证

$$\boxed{\sum _{i=1}^{n}d(i)=\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor }$$

Tip

在具体计算的时候有时由于 $n$ 过大,我们还需要将算法复杂度从 $O(n)$ 降低到 $O(\sqrt{n})$,具体操作可以使用 整除分块

Solution1

void solve()
{
    i64 n;
    cin >> n;
    i64 ans = 0;
    // 注意for中 l 应该是 跳入到下一个块中
    for (i64 l = 1, r; l <= n; l = r + 1) {
        // 当前一个区间的整除数
        i64 k = n / l;
        // 计算块右边界
        r = n / k;
        // 计算结果(不要忘记块长)
        ans += k * (r - l + 1);
    }
    cout << ans << endl;
}