给n个数，m个询问， 问任意区间内与其它数互质的数有多少个
比如3个数1 2 4，询问[1,3] 那么答案是1
千万要记住，这样的题目，如果你不转变下，使劲往线段树想（虽然转变之后，也说要用到线段树，但是维护的东西不同了），那么会发现这样的题目，区间与区间之间是无法传递信息的，
区间与区间是无法传递信息的，区间与区间之间是无法传递信息的，重要的东西说三遍。
设n个数，存在数组a[]里面
我们预处理出，L[],和R[],L[i] 表示从i往左，第一个与a[i]不互质的数的位置+1, R[i]表示从i往右，第一个与a[i]不互质的数的位置-1
即L[i] 表示 [L[i],i]内的所有数都与a[i]互质，R[i]表示[i,R[i]]内的所有数都与a[i]互质
然后我们离线处理，将所有的询问按照左端点排序
然后枚举左端点i，将所有L[j] = i的 [j,R[j]]区间+1，因为当左端点为i时，L[j]=i的数都在各自的有效区间[j,R[j]]里面生效了
当i=询问的区间的左端点时，只要查询右端点被加了多少次就行了。
走过i时，第i个数不再生效，所以将[i,R[i]]区间-1
#include<cstdio>
#include<iostream>
#include<string.h>
#include<algorithm>
#include <vector>
using namespace std;
const int N = + ;
vector<int> prime[N];
vector<int> cL[N];
int a[N],L[N],R[N];
int mark[N];
int tree[N<<],lazy[N<<];
int ans[N];
void pushDown(int rt)
{
if(lazy[rt])
{
lazy[rt<<] += lazy[rt];
lazy[rt<<|] += lazy[rt];
tree[rt<<] += lazy[rt];
tree[rt<<|] += lazy[rt];
lazy[rt] = ;
}
}
void update(int l, int r, int rt, int L, int R, int val)
{
if(L<=l && R>=r)
{
lazy[rt]+=val;
tree[rt] += val;
return;
}
pushDown(rt);
int mid = (l+r)>>;
if(L<=mid)
update(l,mid,rt<<,L,R,val);
if(R>mid)
update(mid+,r,rt<<|,L,R,val); }
int query(int l, int r, int rt, int pos)
{
if(l==r)
{
return tree[rt];
}
pushDown(rt);
int mid = (l+r)>>;
if(pos<=mid)
return query(l,mid,rt<<,pos);
else
return query(mid+,r,rt<<|,pos);
}
struct Node
{
int l,r,id;
bool operator<(const Node&rhs)const
{
return l < rhs.l;
}
}q[N]; void getPrime()
{
for(int i=;i<=;++i)
{
if(!mark[i])
for(int j=i;j<=;j+=i)
{
mark[j] = true;
prime[j].push_back(i);//得到j的所有素数因子i
}
}
}
void init(int n)
{
memset(mark,,sizeof(mark));
for(int i=; i<prime[a[]].size(); ++i)
mark[prime[a[]][i]] = ;
L[] = ;
cL[].push_back();
for(int i=;i<=n;++i)
{
int pos = ;
for(int j=; j<prime[a[i]].size(); ++j)
{
pos = max(pos,mark[prime[a[i]][j]]);
mark[prime[a[i]][j]] = i;
}
L[i] = pos + ;
cL[L[i]].push_back(i);
}
for(int i=;i<N;++i)mark[i] = n + ;
for(int i=;i<prime[a[n]].size(); ++i)
mark[prime[a[n]][i]] = n;
R[n] = n;
for(int i=n-;i>=;--i)
{
int pos = n + ;
for(int j=;j<prime[a[i]].size(); ++j)
{
pos = min(pos,mark[prime[a[i]][j]]);
mark[prime[a[i]][j]] = i;
}
R[i] = pos - ;
}
}
int main()
{
int n,m;
getPrime();
while(scanf("%d%d",&n,&m),n+m)
{
memset(tree,,sizeof(tree));
memset(lazy,,sizeof(lazy));
for(int i=;i<=n;++i)
{
scanf("%d",&a[i]);
cL[i].clear();
}
init(n);
for(int i=;i<m;++i)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id = i;
}
sort(q,q+m);
int cur = ;
//枚举左端点
for(int i=;i<=n;++i)
{
//当左端点为i时，使得所有L[j] = i的数都在各自的区间[j,R[j]]
//所以在[j,R[j]]区间+1
for(int j=;j<cL[i].size(); ++j)
update(,n,,cL[i][j],R[cL[i][j]],);
//当询问的左端点为i时，
while(q[cur].l==i)
{
//只要询问右端点的值就行了，因为每个数都在自己能生效的区间里面+1了
ans[q[cur].id] = query(,n,,q[cur].r);
cur++;
}
//要走过第i个数了，所以第i个数不再生效了,所以将[i,R[i]]区间-1
update(,n,,i,R[i],-);
}
for(int i=;i<m;++i)
printf("%d\n",ans[i]);
}
return ;
}