分析：找到每一个点的左边离他最近的不互质数，记录下标(L数组)，右边一样如此（R数组），预处理
这个过程需要分解质因数O（n*sqrt(n))
然后离线，按照区间右端点排序
然后扫一遍，对于当前拍好顺序的第i个询问，将所有小于r的点加入更新
更新的过程是这样的
（1）对于刚加入点x，树状数组L[x]位置+1 把这个定义为左更新
（2）对于所有R[i]=x的点，树状数组L[i]位置-1，i位置+1 把这个定义为右更新
（3）查询是询问区间 l->r的和
时间复杂度分析，因为每个点左更新，右更新各一次，所以单组测试用例是O（nlogn)的
下面来解释为啥这样更新
查看当前询问 l , r,对于所有小于 l 的点 i，它的所有更新（左更新和右更新）不会影响到树状数组区间 l 到 r 的 和
对于在l,r区间的点 i，如果 R[i]<=r,那么对于区间 l ->r 有 1 的贡献
如果 R[i]>r,对于这个点，只有左更新L[i]+1;
如果 L[i]>=l ，对于查询区间有 1 的贡献
如果 L[i]<l，对于查询区间没有贡献
不难发现，这样对于查询区间有贡献的点，都是会和别人打架的点
所以该查询的答案就是 查询区间长度 - 树状数组区间和
然后以下看代码
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> using namespace std; typedef long long LL; const int N=2e5; const LL mod=1e9+7; int a[N+5],c[N+5]; int f[N+5],h[N+5],k[N+5]; vector<int>g[N+5]; vector<int>b[N+5]; struct Que { int l,r,id; bool operator<(const Que &e)const { return r<e.r; } }q[N+5]; int n,m; bool vis[N+5]; int prime[N+5],cnt,res[N+5]; void add(int x,int t) { for(;x<=n+1;x+=(x&(-x))) c[x]+=t; } int get(int x) { int ans=0; for(;x>0;x-=(x&(-x))) ans+=c[x]; return ans; } int main() { for(int i=2; i*i<=N; ++i) { if(vis[i])continue; for(int j=i*i; j<=N; j+=i) vis[j]=1; } for(int i=2; i<=N; ++i) if(!vis[i])prime[cnt++]=i; for(int i=2; i<=N; ++i) { int t=i; for(int j=0; j<cnt&&prime[j]*prime[j]<=i; ++j) { if(t%prime[j])continue; g[i].push_back(prime[j]); while(t%prime[j]==0)t/=prime[j]; if(t==1)break; } if(!vis[t]&&t!=1) g[i].push_back(t); } while(~scanf("%d%d",&n,&m),n) { memset(f,0,sizeof(f)); memset(c,0,sizeof(c)); for(int i=2; i<=n+1; ++i) { scanf("%d",&a[i]); h[i]=1; k[i]=n+2; } for(int i=2; i<=n+1; ++i) { for(int j=0; j<g[a[i]].size(); ++j) { int x=g[a[i]][j]; h[i]=max(h[i],f[x]); f[x]=i; } } for(int i=1; i<=N; ++i) f[i]=n+2; for(int i=n+1; i>1; --i) { for(int j=0; j<g[a[i]].size(); ++j) { int x=g[a[i]][j]; k[i]=min(k[i],f[x]); f[x]=i; } } for(int i=1;i<=m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i; sort(q+1,q+1+m); for(int i=1;i<=n;++i) b[i].clear(); for(int i=2;i<=n+1;++i)b[k[i]].push_back(i); int x=2; for(int i=1;i<=m;++i) { while(x<=n+1&&x<=q[i].r+1) { add(h[x],1); for(int j=0;j<b[x].size();++j) { int y=b[x][j]; add(h[y],-1); add(y,1); } ++x; } int t=get(q[i].r+1)-get(q[i].l); res[q[i].id]=q[i].r-q[i].l+1-t; } for(int i=1;i<=m;++i) printf("%d\n",res[i]); } return 0; }
原文：http://www.cnblogs.com/shuguangzw/p/5272595.html
