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;
}
0 条评论