LInk
首先我们可以注意到,两个数的gcd要不是它们当中较小的那一个要不是它本身。
所以对于一个特定的 \(r\),\(gcd_{i=p}^r,1<=p<=r\)来说，答案不会超过32种。
并且因为gcd的性质，答案一定是成块且递减的。
所以我们可以直接记录下对于每一个\(r\),答案都有哪些，从哪里开始出现。
并且\(r+1\)的值可以从\(r\)推出。
最后只要对于所有可能的答案进行判断就可以了。
\(O(32n)\)的时间复杂度
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n,m;
int ans[600005][33];
int v[600005][33];
int a[600005];
int l,r;
map<int,int> mp;
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i){
ans[i][0]++;
ans[i][1]=i;
v[i][1]=a[i];
mp[a[i]]=i;
for(int j=1;j<=ans[i-1][0];++j){
int vv=gcd(a[i],v[i-1][j]);
if(!mp.count(vv)||mp[vv]!=i){
mp[vv]=i;
ans[i][0]++;
ans[i][ans[i][0]]=ans[i-1][j];
v[i][ans[i][0]]=vv;
}
}
}
while(m--){
scanf("%d%d",&l,&r);
int cnt=1;
int cntt=0;
while(cnt<=ans[r][0]){
if(l<=ans[r][cnt]){
cntt++;
}
cnt++;
}
printf("%d\n",cntt);
}
return 0;
}