imicola 约数
约数

约数

408 字 · 约 1 分钟

约数个数和定理

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

∑i=1nd(i)=∑i=1n⌊ni⌋\sum\limits^{n}_{i = 1}d(i) = \sum\limits^{n}_{i = 1}\left\lfloor \frac{n}{i} \right\rfloor
这个等式的证明如下

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

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

∣S∣=∑i=1nd(i)(1)|S| = \sum\limits^{n}_{i=1}d(i) \tag{1}
按固定的aa 角度
固定a∈[1,n]a \in [1,n],则满足条件的bb的个数是满足 ab≤nab \leq n的个数,即:
{b∣b≥1 and b≤na}=⌊na⌋\{b | b \geq1 \text{ and } b \leq \frac{n}{a}\} = \left\lfloor \frac{n}{a} \right\rfloor
累加有:
∣S∣=∑a=1n⌊na⌋(2)|S| = \sum\limits^{n}_{a=1} \left\lfloor \frac{n}{a} \right\rfloor \tag{2}

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

∑i=1nd(i)=∑i=1n⌊ni⌋\boxed{\sum\limits^{n}_{i = 1}d(i) = \sum\limits^{n}_{i = 1}\left\lfloor \frac{n}{i} \right\rfloor}

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;
}
cpp

知识关联

1 反向链接 · 1 提及笔记
局部关系图谱 悬停高亮 · 点击跳转