D. Cut(质因子分解，倍增)

D. Cut

题意：给出一个长度为n的序列，和q个询问，对于每个询问，求出最少分成多少个连续的子区间，使每个子区间的$lcm$等于子区间各个数的乘积。

思路：质因子分解+倍增思想。

1. 预处理：利用质因子分解来找当前元素能够向后跳到的最远的位置（满足从开始位置到结束位置中的每个元素都互质）

2. 利用倍增的思想，来加速跳的过程。

3. 对于每个询问，只要从没有跳到边界，就一直往下跳，直到位置大于右边界，跳的次数加一就时答案。

预处理：$dp[i][0]$表示区间$[i，dp[i][0]]$中所有的元素都是互质的。

倍增：$dp[i][j]$表示从$i$开始跳$2^j$次，跳到的位置(注意每次跳的长度不一定是相同的)，也就是分成了$2^j$个区间。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int s[N], ne[N], dp[N][20];
unordered_map<int, int> p;
int main() {
#ifndef ONLINE_JUDGE 
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    memset(ne, 0x7f, sizeof ne);
    int n, m, x, y;
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> s[i];
    }
    //预处理
    dp[n+1][0] = n+1;
    for(int i=n; i>=1; i--) {
        int tmp = s[i];
        dp[i][0] = dp[i+1][0]; //继承前一个元素能到到最大位置。
        for(int j=2; 1ll*j*j<=tmp; j++) {//质因子分解
            if(tmp % j == 0) {
                if(p[j]) ne[i] = min(p[j], ne[i]);//判断之前是否出现过这个素数。
                p[j] = i;//标记
                while(tmp % j == 0) tmp /= j;
            }
        }
        if(tmp > 1) {
            if(p[tmp]) ne[i] = min(p[tmp], ne[i]);
            p[tmp] = i;
        }
        if(ne[i] == 2139062143) ne[i] = n+1;
        dp[i][0] = min(ne[i], dp[i][0]);//取最小值，为了使从开始位置到结束位置中的每个元素都互质
    }
    for(int i=n+1; i>=1; i--) {
        for(int j=1; j<=17; j++) {//倍增思想。
            dp[i][j] = dp[dp[i][j-1]][j-1];
        }
    }
    //每个询问
    for(int i=1; i<=m; i++) {
        cin >> x >> y;
        int ans = 0;
        for(int i=17; i>=0; i--) {//可以证明，下一个位置能够跳的次数一定小于之前跳的次数。
            if(dp[x][i] <= y) {
                ans += (1<<i);
                x = dp[x][i];
            }
        }
        cout << ans+1 << endl;
    }
    return 0;
}