CF1516D. Cut

题目大意

给你一个 n 个数的序列 a_i​，和 q 次询问，每次询问一段区间 [l,r]，问至少要把这个区间分为几个子区间，才能使得每个子区间内的数的乘积等于这个子区间内所有数的 LCM 。

n,a_i,q\le 10^5

Solution

我们可以通过双指针或者从后向前枚举，预处理出每个元素后第一个与他不互质的元素的坐标。

（官方题解给的预处理的方式很巧妙，看看下面的代码应该就能明白了）

然后利用倍增思想解决问题，用 dp[i][j] 表示从 i 开始，分成 2^j 段 ，所能到达的坐标位置 + 1。

然后每次倍增处理就好

#include<bits/stdc++.h>
const int N = 100100;
using namespace std;
vector<int> vec[N];
int nxt[N],dp[N][21],n,q,a[N];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=2;i<N;++i){
        if(!vec[i].empty()) continue;
        nxt[i]=n+1;
        for(int j=i;j<N;j+=i)
            vec[j].push_back(i);
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);  
    dp[n+1][0]=n+1;
    for(int i=n;i;--i){
        dp[i][0]=dp[i+1][0];
        for(auto p:vec[a[i]]){
            dp[i][0]=min(dp[i][0],nxt[p]);
            nxt[p]=i; 
        }
    }
    for(int i=1;i<20;++i){
        for(int j=1;j<=n+1;++j)
            dp[j][i]=dp[dp[j][i-1]][i-1];
    }
    while(q--){
        int l,r,ans=1;
        scanf("%d%d",&l,&r);
        for(int i=19;i+1;--i){
            if(dp[l][i]<=r){
                l=dp[l][i];
                ans+=1<<i;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}