题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4777
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
typedef pair<int,int> pii;
const int maxn =2e5+7;
const int mod=1e9+7;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：已知一只兔子的重量如果不是和另外一只 是互质关系，
那么他们就会打架，现在有一个兔子的重量序列，给定若干个查询，
对于每个查询，问有多少个兔子不会打架。太弱了，，，看题解才明白思路，
并且自己写写出来个爆空间的代码，。。。T_T无语
大致思路就是，先把每个数的左右边界找好，就是
说一个数在什么范围内一定是安全的，
对于左右边界，我们建立些映射关系，
左边界映射到当前点，当前点可以映射到左右边界（单射）,
然后分析这样处理后如何丢到树状数组中，
首先按l排序离线处理，对于左边的数字，
假设他们是一些数的左边界，那么这些左边界映射出来的点产生的贡献就可以
加一，然后其右边界产生的点的贡献需要递减一个，
当然，为防止右边界的贡献有时候会影响答案，对于扫描过的
数字，其右边界的贡献加一。整体想法有点DP的味道在里面。。。
（下述代码空间爆了，，，后期有空再处理吧。。。）*/int n,m,a[maxn];
int ret[maxn];
struct qy{int l,r,id;bool operator<(const qy& y) const{if(l==y.l) return r<y.r;return l<y.l;}
}q[maxn];vector<int> yinzi[maxn],C[maxn];///因子集合
int pos[maxn];///所有因子的最近出现位置
int L[maxn],R[maxn];///最左端，最右端的位置///树状数组结构
int bit[maxn];
int lowbit(int x){return x&(-x);}
void add(int x,int d){for(;x<maxn;bit[x]+=d,x+=lowbit(x));}
int sum(int x){int rt=0;for(;x>0;rt+=bit[x],x-=lowbit(x));return rt;}void init()
{for(int i=0;i<=n;i++) C[i].clear();memset(bit,0,sizeof(bit));memset(pos,0,sizeof(pos));for(int i=0;i<maxn;i++) R[i]=n+1,L[i]=0;///初始化for(int i=1,ai=a[i];i<=n;i++,ai=a[i]){for(int j=0;j<yinzi[ai].size();j++){L[i]=max(L[i],pos[yinzi[ai][j]]);pos[yinzi[ai][j]]=i;}C[L[i]].push_back(i);///以L[i]为左端点的有哪些坐标}for(int i=0;i<maxn;i++) pos[i]=n+1;for(int i=n,ai=a[i];i>=1;i--,ai=a[i]){for(int j=0;j<yinzi[ai].size();j++){R[i]=min(R[i],pos[yinzi[ai][j]]);pos[yinzi[ai][j]]=i;}}
}int main()
{for(int i=2;i<maxn;i++) for(int j=i;j<maxn;j+=i) yinzi[j].push_back(i);while(scanf("%d%d",&n,&m) && (n||m)){for(int i=1;i<=n;i++) scanf("%d",&a[i]);///数据数组for(int i=0;i<m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;sort(q,q+m);///将询问排序init();///初始化int cur=0;for(int i=0;i<m;i++){while(cur<q[i].l){for(int j=0;j<C[cur].size();j++)add(C[cur][j],1),add(R[C[cur][j]],-1);if(R[cur]) add(R[cur],1);cur++;}ret[q[i].id]=sum(q[i].r)-sum(q[i].l-1);}for(int i=0;i<m;i++) printf("%d\n",ret[i]);}return 0;
}