题解：CF2094H La Vaca Saturno Saturnita

biyi_mouse · 2025-05-06 16:51:48 · 题解

根号分治题，可惜我没做出来（其实主要还是没想到第二种预处理）。

对于一个询问显然直接循环做没有前途，原因是会遍历很多 useless 状态无法改变 k。不妨考虑如何快速从一个 useful 状态跳到另一个 useful 状态。

首先会发现 k \leq 100000，这代表所有询问实际上都比较小，所以它们的约数也都比较小。比较自然的有一种类似序列自动机的预处理，设 ne_{i, j} 为 i 及它后面 j 第一次出现的位置。转移是轻松的。

这样做是 O(nV) 的。我们考虑这个做法的瓶颈在于值域 V 太大了，所以我们不妨根号分治。只处理值域 \leq B 的情况。而对于值域 > B 的情况我们可以类似筛法地把求出 pos_x 表示 x 在 a 中的所有因数。

然后对于询问，按照最开始提到的思路做即可。需要注意的是我们每次需要在 pos 中二分，所以还要加个 \log。整个时间复杂度是 O(nB + \frac{nV}{B} + q\log V(\log n + B))。B 随便取个 250 就跑的很快了。

const int N = 100010, B = 250;
int n, q, a[N];
int ne[N][B];
vector<int> divs[N], pos[N];

void solve() {
    n = read(), q = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    for (int i = 1; i <= B; i ++) ne[n + 1][i] = n + 1;
    for (int i = 1; i <= n; i ++) {
        if (a[i] > B) 
            for (int j = a[i]; j <= N - 10; j += a[i])
                pos[j].push_back(i);
    }
    for (int i = n; i >= 1; i --) {
        for (int j = 1; j <= B; j ++) ne[i][j] = ne[i + 1][j];
        if (a[i] <= B) ne[i][a[i]] = i;
    }
    while (q --) {
        int k = read(), l = read(), r = read();
        LL ans = 0;
        for (int p = l; ; ) {
            int R = r + 1;
            for (auto x : divs[k]) 
                if (x <= B) R = min(R, ne[p][x]);
            auto it = lower_bound(pos[k].begin(), pos[k].end(), p);
            if (it != pos[k].end()) R = min(R, *it);
            ans += 1ll * (R - p) * k;
            p = R;
            if (p > r) break;
            while (k % a[p] == 0) k /= a[p];
        }   
        printf("%lld\n", ans);
    }
    for (int i = 1; i <= n; i ++) {
        if (a[i] > B) 
            for (int j = a[i]; j <= N - 10; j += a[i])
                pos[j].clear();
    }
}

int main() {
    for (int i = 2; i <= N - 10; i ++)
        for (int j = i; j <= N - 10; j += i)
            divs[j].push_back(i);
    int T = read(); 
    while (T --) solve();
    return 0;
}