描述：

给定 \(n\) 个数的序列和 \(q\) 次询问，每次询问给定区间 \([l,r]\) ，求出至少将其分割成几个子区间，才使得每个子区间的 \(\operatorname{lcm}\) 等于区间内所有数的乘积。

思路：

区间 \([l,r]\) 内所有数的乘积等于其 \(\operatorname{lcm}\) 当且仅当 \(\gcd(a_i,a_j)=1\) ，其中 \(i\neq j,\; i,j \in [l,r]\) 。

那么可以对于每次给出的区间 \([l,r]\) 从左到右暴力扫一遍，过不去，考虑优化。

可以预处理每个左端点 \(i\) 所对应的最靠右的右端点 \(nex(i)\) 。

从左到右枚举 \(i\) ，发现 \(nex(i) \ge nex(i-1)\) ，因为少了 \(1\) 个数，右端点必定不会更近。

那么就可以 \(O(n)\) 双指针预处理 \(nex(i)\) 。

对于如何判断两两互质，可以用线性筛预处理出 \(10^5\) 以内的质数，再枚举每个质数 \(j\) ，对于其倍数 \(i\) ，\(i \le 10^5\) ，将 \(j\) 加入 \(i\) 的 质因数集合，换个顺序，就可以从 \(O(n\sqrt{n})\) 变成 \(O(n\log n)\) 。

如果从 \(l\) 开始，往右边跳的话，如果它们都互相不互质，单次就变成 \(O(n)\) 了。

容易想到，可以用倍增优化，单次就变成 \(O(\log n)\) 。

总时间复杂度 \(O(n)+O(n\log n)+O(n\log n)=O(n\log n)\) 。

\(\mathtt{Ps:}\)

\(nex(i)\) 表示的不是以 \(i\) 为左端点的最靠右的右端点，而是下一个区间的左端点。

预处理 \(st(i,j)\) 时，必须要加上 \(st(k,n+1)\) 为 \(n+1\) ，否则其值为 \(0\) ，可能会一直跳到 \(2^m\) 。

代码：

Prime 预处理质数

Calc 判断当前的 \(a_j\) 能否加入

Del 删除 \(a_{i-1}\)

Ask 倍增查询答案，注意最后一定要加 \(1\)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

#define LL long long
#define PR pair<LL,int>

using namespace std;

const int kN = 1e5;

int n, a[kN + 10], q;
int prime[kN + 10], tot;
int nex[kN + 10], st[30][kN + 10];
int _2[30], num[kN + 10];

vector<int> e[kN + 10];

bool isp[kN + 10];

void Prime() {
    isp[1] = 1;

    for (int i = 2; i <= kN; ++i) {
        if (!isp[i]) {
            prime[++tot] = i;
        }

        for (int j = 1; j <= tot && prime[j]*i <= kN; ++j) {
            isp[i * prime[j]] = 1;

            if (i % prime[j] == 0) {
                break;
            }
        }
    }

    for (int i = 1; i <= tot; ++i) {
        for (int j = prime[i]; j <= kN; j += prime[i]) {
            e[j].push_back(i);
        }
    }
}

bool Calc(int x) {
    for (int i = 0; i < e[x].size(); ++i) {
        int k = e[x][i];

        if (num[k]) {
            return 0;
        }
    }

    for (int i = 0; i < e[x].size(); ++i) {
        int k = e[x][i];
        num[k] = 1;
    }

    return 1;
}

void Del(int x) {
    if (!x) {
        return;
    }

    for (int i = 0; i < e[x].size(); ++i) {
        int k = e[x][i];
        num[k] = 0;
    }
}

int Ask(int l, int r) {
    int cnt = 0;

    for (int i = 20; i >= 0; --i) {
        if (st[i][l] <= r) {
            l = st[i][l];
            cnt += _2[i];
        }
    }

    return cnt + 1;
}

int main() {
    scanf("%d%d", &n, &q);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }

    Prime();
    _2[0] = 1;

    for (int i = 1; i <= 20; ++i) {
        _2[i] = _2[i - 1] * 2;
    }

    for (int i = 1, j = 0; i <= n; ++i) {
        Del(a[i - 1]);

        while (j < n && Calc(a[j + 1])) {
            j++;
        }

        nex[i] = j + 1;
        st[0][i] = nex[i];
    }

    st[0][n + 1] = n + 1;

    for (int i = 1; i <= 20; ++i) {
        st[i][n + 1] = n + 1;

        for (int j = 1; j <= n; ++j) {
            st[i][j] = st[i - 1][st[i - 1][j]];
        }
    }

    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", Ask(l, r));
    }

    return 0;
}