题意：
给定 $N$ 个数字， $Q$ 次询问，每次询问为查询下标在 $[l,r]$ 之间的所有数字中所有可能的子段的 $gcd$ 有多少种。$N,Q < 10^5 , a_i < 10^6$
题解：
首先一个重要的结论：以固定点为结尾的子段的 $gcd$ 种数不超过 $max(n,log(max(a_i)))$ 证明：每次往原有的序列里加入一个数字的话， $gcd$ 要么不变，要么至少变为原来的1/2，因此为指数级减小。
有了这个结论，我们可以试着来枚举一个端点考虑本题，不妨枚举每个段的右端点$r_j$ , 假设集合$S$表示以$r_{j-1}$ 为结尾的所有 $gcd$ ，那么要求出以$r_j$为结尾的所有 $gcd$ ，只需遍历S中的每个数字$d_k$，计算其与$a_j$ 的 $gcd$ ，放入新集合$S^{‘}$即可。这样的话我们可以得到一个空间为$O(nlogn)$的结果，表示以每个点为结尾的所有段的 $gcd$ 都是哪些数字。
现在来考虑查询。每次查询的话是要求出来$[l,r]$之间所有可能的 $gcd$ 。直接暴力不可取，由上面的结果可以试着考虑能否转化为前缀问题。可以发现，如果我们对所有的$[l,r]$离线处理，按$r$从小到大排序，并且按照这个顺序来调整已经遇到过的 $gcd$ 的信息的话，每次的查询只需要考虑有多少个 $gcd$ 出现的最右左端点大于等于l，这句话具体的意思是，一个 $gcd$ 可能出现过了很多次，不同的段都可以得到这个 $gcd$ ，但是我们只考虑这些段中左端点l_j最大的那个点$p_j$，这样的话如果$l<=p_j$那么可以确定$[l,r]$中一定有这个 $gcd$ （种类+1），这就就转化成了一个计数问题。
那么考虑如何来维护这个每个 $gcd$ 及其最右左端点。从我们推$O(nlogn)$的以每个点位结尾的 $gcd$ 集合来看，只需要在这个过程中为每个 $gcd$ 多维护一个表示最右左端点的域即可，更新就是把每次新产生的（以前从来没有见过的） $gcd$ 的这个域设为当前的下标i，其他的保持不变即可。由于$a_i$的最大值只有$10^6$，可以直接用一个数组$has[d]$来维护到目前为止$d$作为某个段的 $gcd$ 出现的最右位置。至于前后集合的递推可以用滚动数组，考虑到去重的话用两个$map$替代两个数组即可。
代码的话想清楚之后实现还是很简单的。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
int N,Q,MX;
map<int,int> mp[2];
map<int,int>::iterator it;
int has[maxn*10];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
vector<pair<int,int> > qs[maxn];
int tr[maxn*20];
void change(int x,int p){
while(x<=MX){
tr[x]+=p;
x+=(x&(-x));
}
}
ll sum(int x){
ll res=0;
while(x>0){
res+=tr[x];
x-=(x&(-x));
}
return res;
}
void move(int a,int b){
change(a,-1);
change(b,1);
}
int a[maxn],ans[maxn];
void init(){
for(int i=0;i<=N;i++) qs[i].clear();
mp[0].clear(),mp[1].clear();//final error
memset(tr,0,sizeof(tr));
memset(has,0,sizeof(has));
MX=0;
}
int main(){
int l,r,tmp,id,pt,pos;
while(~scanf("%d%d",&N,&Q)){
init();pt=0;
for(int i=1;i<=N;i++){
scanf("%d",&a[i]);
MX=max(MX,a[i]);
}
for(int i=1;i<=Q;i++){
scanf("%d%d",&l,&r);
qs[r].push_back(make_pair(l,i));
}
for(int i=1;i<=N;i++,pt^=1){
int len=qs[i].size();
mp[pt].clear();
mp[pt][a[i]]=i;
for(it=mp[pt^1].begin();it!=mp[pt^1].end();++it){
tmp=gcd(a[i],it->first);
if(mp[pt].find(tmp)!=mp[pt].end()){
mp[pt][tmp]=max(mp[pt][tmp],it->second);
}else{
mp[pt][tmp]=it->second;
}
}
for(it=mp[pt].begin();it!=mp[pt].end();++it){
tmp=it->first,pos=it->second;
if(has[tmp]){
if(has[tmp]==pos) continue;
move(min(has[tmp],pos),max(has[tmp],pos));
has[tmp]=max(has[tmp],pos);
}else{
change(pos,1);
has[tmp]=pos;
}
}
if(len){
for(int j=0;j<len;j++){
l=qs[i][j].first,id=qs[i][j].second;
ans[id]=sum(i)-sum(l-1);
}
}
}
for(int i=1;i<=Q;++i){
printf("%d\n",ans[i]);//error2
}
}
return 0;
}