用BIT或线段树维护的神马东西，碰到这种东西智商就没有了……
看了网上的基本所有博客，终于想明白了，
最终又看了kuangbin简单的总结：
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#include<string>
using namespace std;
#define inf 0x3f3f3f
#define ll __int64
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const ll mod=1e9+7;
int p[200020];
struct node
{
int l,r,index;
}h[200020];
int L[200020],R[200020];
vector<int> f[200020];
vector<int> ft[200020];
int vis[200020];
void init()
{
int i,j;
for(i=2;i<=200000;i++)//nlog(n)求i的所有因子
for(j=i;j<=200000;j+=i)
f[j].push_back(i);
}
bool cmp(node a,node b)
{
return a.r<b.r;
}
int in[200020];
int lowbit(int t)
{
return t&(-t);
}
int Sum(int t)
{
int sum=0;
while(t>0)
{
sum+=in[t];
t-=lowbit(t);
}
return sum;
}
void add(int t,int num)
{
if(t==0) return ;
while(t<=200020)
{
in[t]+=num;
t+=lowbit(t);
}
}
int ans[200020];
int main()
{
int n,m;
int i,j,k;
init();
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
for(i=1;i<=n;i++) scanf("%d",&p[i]);
for(i=1;i<=m;i++)
{
scanf("%d%d",&h[i].l,&h[i].r);
h[i].index=i;
}
mem(vis,0);
for(i=1;i<=n;i++)
{
L[i]=0;
int len=f[p[i]].size();
for(j=0;j<len;j++)
{
L[i]=max(L[i],vis[f[p[i]][j]]);
vis[f[p[i]][j]]=i;
}
}
mem(vis,inf);
for(i=n;i>=1;i--)
{
R[i]=n+1;
int len=f[p[i]].size();
for(j=0;j<len;j++)
{
R[i]=min(R[i],vis[f[p[i]][j]]);
vis[f[p[i]][j]]=i;
}
}
sort(h+1,h+1+m,cmp);
int id=1;
mem(in,0);
for(i=0;i<=n+2;i++)
ft[i].clear();
for(i=1;i<=n;i++)
ft[R[i]].push_back(i);
for(i=1;i<=m;i++)
{
while(id<=n && id<=h[i].r)
{
add(L[id],1);
int len=ft[id].size();
for(j=0;j<len;j++)
{
int v=ft[id][j];
add(L[v],-1);
add(v,1);
}
id++;
}
ans[h[i].index]=h[i].r-h[i].l+1-(Sum(h[i].r)-Sum(h[i].l-1));
}
for(i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
}