wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

同余与模

同余与模的应用

同余与模的概念

特殊的数

斯特林数

斯特林数相关的恒等式

斯特林数的综合应用

FFT的应用

整除分块

[[ item.c ]]

整除分块

## 整除分块
整除分块可以处理类似
```math
\displaystyle
\sum\left( \lceil \dfrac{a_i}{k}\rceil - \lceil \dfrac{a_{i-1}}{k} \rceil \right)
```
或者对$$\sum (n \bmod i)$$之类的问题

### 引入
**[智乃与模数](https://ac.nowcoder.com/acm/contest/95335/G)**
输入一个`n`，现在把所有的`i = {1, 2, ..., n}`，求$$(n \bmod i)$$，然后将结果单调递减排列
求前`k`个数的和

**算法分析**
求类似$$\sum (n \bmod i)$$，考虑整除分块

**性质**
1）每一个块的元素，$$i \in [l, r]$$，$$\lfloor \dfrac{n}{i} \rfloor$$的结果都是$$v = \lfloor \dfrac{n}{l} \rfloor$$

2）每一个块，$$(n \bmod i)$$即**余数呈等差数列**，并且按递减顺序排列

余数分别是
```bash
块 [l, r]，商是 v = (n / l)
余数按等差数列递减排列
{n-lv,  n-(l+1)v, n-(l+2)v, ....., n-rv}
```

回到这个问题，前`k`个数的和怎么求呢？我们需要知道前`k`个数对应的$$n \bmod i$$**余数是多少**
假设说我们钦定余数是$$t$$，那么我们需要确定，**余数**$$\geqslant t$$的数有多少个？

不难想到**二分余数**，二分**最后一个**`r`，使得$$1\sim n$$的所有数中
满足`n mod (这些数)`的余数$$\geqslant r$$的“这些数”有$$< K$$个，具体有多少个呢？假设说`cnt`个
那么还差$$K - cnt$$个，此时令`r -= 1`，就一定可以

最后一小段余数都是`r - 1`，恰好有$$K - cnt$$个

> 接下来考虑`check(余数) = 有多少个 [1, n] 中的数满足，(n mod 这些数) >= 余数`

![](/media/content_img/divBlock.png)

其中`check`很好写，遍历每一个块依次计算即可，求和也不难，是朴素的等差数列求和
最后剩余的`mod = r - 1`填充到`K`，不会取遍所有的数，而只会取一部分
好在这些数的余数都相等，都是`r - 1`，只需要`K - cnt`个，还缺少的贡献是`(K - cnt) * (r - 1)`
把这部分缺少的加上即可

### 算法实现
```bash
using arr = array<int, 3>;
 
void solve() {
    int n, k;
    cin >> n >> k;
 
    vector<arr> block;
 
    for (int l = 1, r; l <= n; l = r + 1) {
        int v = n / l;
        r = n / v;
 
        block.push_back({l, r, v});
    }
 
    auto check = [&](int mod) {
        int cnt = 0;
        i64 sum = 0;
        for (auto [l, r, v] : block) {
            auto p = (n - mod) / v;
            p = min(p, r);
 
            if (l > p) continue;
 
            cnt += p - l + 1;
            sum += (i64)(p-l+1) * n - (i64)(l+p) * (p-l+1) * v / 2;
        }
        return pair(cnt, sum);
    };
 
    int l = 0, r = n;
    while (l < r) {
        auto mid = (l + r) >> 1;
        auto [cnt, sum] = check(mid);
 
        if (cnt < k) r = mid;
        else l = mid + 1;
    }
 
    auto mod = r;
    auto [cnt, sum] = check(mod);
 
    if (k > cnt) {
        auto d = k - cnt;
        sum += (i64)(mod - 1) * d;
    }
 
    cout << sum << "\n";
}
```

看完文章有啥想法

算法小站

wiki 主题

数学

整除分块

目录