题目描述

这一次，Baby Ehab 只会剪纸而不会粘贴。他开始时有一张纸，上面写着一个长度为 $n$ 的数组 $a$ ，然后他会进行如下操作：

他选择一个区间 $(l, r)$ ，将子段 $a_l, a_{l + 1}, \ldots, a_r$ 剪下来，移除数组的其他部分。
然后，他将这个区间再切分成若干个子区间。
为了增加一点数论的趣味，他要求每个子区间内所有元素的乘积必须等于它们的最小公倍数（LCM）。

形式化地说，他需要将 $a_l, a_{l + 1}, \ldots, a_r$ 划分为若干个连续的子数组，使得每个子数组的所有元素的乘积等于它们的最小公倍数。现在，对于 $q$ 个独立的区间 $(l, r)$ ，请你告诉 Baby Ehab 至少需要将该区间划分为多少个这样的子数组。

$1 \le n, q \le 10^5$ ， $1 \le a_i \le 10^5$

思路

我们先来思考这样一个问题：如何求出以 $i$ 位置为左节点，另一个满足条件的右节点位置的下一格最远在哪里？

首先不难想到的是，这个位置不能超过 $i+1$ 所对应的位置。

其次把 $a_i$ 分解质因数，对于每个分解出来的质数，选择的位置不能超过它上一次出现的位置。

可以用埃筛预处理可能出现的每个数的质因数，这里 $a_i$ 最多到1e5，完全能跑，接着把数组倒着遍历一遍就可以。

然后可以倍增， $f_{i,j}$ 表示 $i$ 结点跳 $2_j$ 步会到哪一个结点，那 $f_{i,j}$ 应该就是 $f_{f_{i, j - 1}, j - 1}$ ，相当于跳了两次 $2^{j - 1}$ 步，也就是 $2_j$ 步。

现在问题来到了怎么查询 $[l,r]$ 之间的答案，可以直接从大道小枚举二进制的位数 $i$ ，要是当前的 $l$ 跳 $2^{i}$ 步不会超过 $r$ ，那么我们就更新 $l$ 到 $f_{l, i}$ 并把答案加上 $2^i$ 。

然后就不知道写什么了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> d[100005];
int f[100005][30];
int pos[100005];
signed main()
{   
    d[1].push_back(1);
    for (int i = 2; i <= 100000; i++) {
        if (d[i].empty()) {
            for (int j = 1; i * j <= 100000; j++) {
                d[i * j].push_back(i);
            }
        }
    }
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    f[n][0] = n;
    memset(pos, 0x3f3f3f3f, sizeof(pos));
    for (int i = n - 1; i >= 0; i--) {
        f[i][0] = f[i + 1][0];
        for (int j = 0; j < d[a[i]].size(); j++) {
            f[i][0] = min(f[i][0], pos[d[a[i]][j]]);
            pos[d[a[i]][j]] = i;
        }
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j <= n; j++) {
            f[j][i] = f[f[j][i - 1]][i - 1];
        }
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        int ans = 0;
        for (int i = 19; i >= 0; i--) {
            if (f[l][i] <= r) {
                l = f[l][i];
                ans += (1 << i);
            }
        }
        cout << ans + 1 << '\n';
    }
    return 0;
}