区间GCD分块

引言

区间GCD分块就是将前/后缀的GCD数组按照数值分块。

其数学原理是，对于任意长度的数组 ，固定其一端点后，不断向另一端延伸构成的前缀（或后缀）区间，其产生的不同 GCD 值的个数至多为 个，其中 是数组元素的最大值。

这里有两种方法，第一种是二分加st表的方法，时间复杂度为 ，第二种是离线的方法，时间复杂度为 ，解决一些问题的时候更优。

正文

例题

【题目描述】

给定一个长度为 的正整数数组 。现在有 次独立询问，每次询问给定一个整数 。对于每个询问，你需要回答：数组中有多少个连续子区间 （），满足该区间的 ？

【数据范围】

询问的

第一种做法

st表可以快速得到区间gcd。对于任意一个区间，由于区间中的前/后缀gcd值最多只有 种，因此，我们可以二分查找前/后缀gcd值相同的边界，二分的时间复杂度是 。

对于例题，我们可以枚举所有的区间左边界，然后对前缀gcd进行分块，找到gcd值为 的右端点区间，得到答案。

第二种做法

这种做法有点像第一种做法的逆向思维，它不是固定一个点不动，然后让其往一个方向蔓延来找区间，而是一个一个的将点加入进已经分好的块中。

具体来说，我们从左到右扫描数组，然后维护一个以这个点为起点，所造成的后缀gcd分块。

由于口述不太好理解，我用AI举了个例子，帮助理解具体的过程。

点击展开

请把视线聚焦在下面的“📦 块列表”上，看它们是怎么变化和融合的：

初始状态：数组 A = [12, 6, 18, 40]

⏱️ 第一步：扫描线来到位置 1（当前数字：12） 此时只有一个数字，自成一派。

  • 📦 当前块列表：
    • [块A] 左边界:1 | 右边界:1 | GCD值: 12

⏱️ 第二步：扫描线来到位置 2（当前数字：6） 现在，我们要把新来的 6 滴加到前面的块里。

  • 反应：旧的 [块A] 里的 12 遇到 6，。
  • 新兵：新位置 2 的数字自己形成一个值为 6 的区域。
  • 💥 发生融合：因为前面的块变成了 6，新来的也是 6，连成一片了！
  • 📦 当前块列表（更新后）：
    • [块A] 左边界:1 | 右边界:2 | GCD值: 6
    (潜台词：管你是从 1 开始还是 2 开始，走到现在，GCD 都是 6！)

⏱️ 第三步：扫描线来到位置 3（当前数字：18） 把新来的 18 滴加到前面的块里。

  • 反应：旧的 [块A] 里的 6 遇到 18，。（没变）
  • 新兵：新位置 3 的数字自己形成一个值为 18 的区域。
  • 观察：前面的值为 6，后面的值为 18。不一样，无法融合。
  • 📦 当前块列表（更新后）：
    • [块A] 左边界:1 | 右边界:2 | GCD值: 6
    • [块B] 左边界:3 | 右边界:3 | GCD值: 18

⏱️ 第四步：扫描线来到位置 4（当前数字：40） 👈 最神奇的一步！ 把新来的 40 滴加到前面所有的块里。

  • 反应 1：旧的 [块A] (值6) 遇到 40，。
  • 反应 2：旧的 [块B] (值18) 遇到 40，。
  • 新兵：新位置 4 的数字自己形成一个值为 40 的区域。
  • 💥 发生超级融合：你发现了吗？原本不一样的 [块A] 和 [块B]，在遇到 40 之后，它们的 GCD 都变成了 2！既然数值一样，并且物理位置是挨着的（12 和 33），立刻吃掉边界，融合成一个大块！
  • 📦 当前块列表（最终更新）：
    • [超级块A] 左边界:1 | 右边界:3 | GCD值: 2
    • [块B] 左边界:4 | 右边界:4 | GCD值: 40
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q, x;
    cin >> n;
    vector<int> a(n);
    map<int, ll> cnt;
    for (auto &i : a) cin >> i;

    vector<array<int, 3>> block, b;
    for (int i = 0; i < n; i ++) {
        block.push_back({i, i, a[i]});
        for (auto& [l, r, val] : block) {
            val = __gcd(a[i], val);
            cnt[val] += r - l + 1;
            if (b.empty() || b.back()[2] != val) b.push_back({l, r, val});
            else b.back()[1] = r;
        }
        block = move(b);
    }

    cin >> q;
    while (q --) {
        cin >> x;
        cout << cnt[x] << '\n';
    }

    return 0;
}