题意:给了n个数，然后又m次查询，询问[L,R] 内有多少个数与其他的数不互质。
解:
我们首先可以通过处理得出每个数的有效区间，LR 就是 左边L位置上的数 和他不互质， 右边R位置上的数和不互质，
我们对于询问排序，R小的排前面，枚举每个R，在loc位置就将第loc个点在loc的位置加上一个1在loc的L(左不互质点)减一个1,再将枚举到该位的时候对于有在这个位置上R的点 在loc位置减1
在loc的L位置加1
#include <iostream> #include <algorithm> #include <cstdio> #include <string.h> #include <vector> #include <cmath> using namespace std; const int maxn=200005; typedef long long LL; bool vis[maxn]; int yinzi[maxn][10],numofYZ[maxn]; void sieve() { memset(vis,false,sizeof(vis)); memset(numofYZ,false,sizeof(numofYZ)); for(LL i=2; i<=200000; i++) { if(vis[i])continue; yinzi[i][numofYZ[i]++]=i; for(LL j=i+i; j<=200000; j+=i) { vis[j]=true; yinzi[j][numofYZ[j]++]=i; } } } struct point{ int L,R,id; bool operator <(const point &rhs)const { return R<rhs.R||( R == rhs.R && L<rhs.L); } }wLR[maxn],Q[maxn]; int Loc[maxn]; int w[maxn]; vector<int>G[maxn]; void init(int n) { for(int i=0; i<=n+1; i++) G[i].clear(); } int n,m; int C[maxn]; int lowbit(int x) { return x&(-x); } void add(int x,int v) { if(x<=0)return ; while(x<=n) { C[x]+=v; x+=lowbit(x); } } int sum(int x) { int ans=0; while(x>0) { ans+=C[x]; x-=lowbit(x); } return ans; } int ans[maxn]; int main() { sieve(); while(scanf("%d%d",&n,&m)==2&&n) { int maW=0; for(int i=1; i<=n; i++) { scanf("%d",&w[i]); maW=max(maW,w[i]); } memset(Loc,0,sizeof(Loc)); for(int i=1; i<=n; i++) { int ww=w[i]; int L=0; for(int j=0; j<numofYZ[ ww ]; j++) L=max(L,Loc[ yinzi[ ww ][ j ] ]); wLR[i].L=L; for(int j=0; j<numofYZ[ ww ]; j++) Loc[ yinzi[ ww ][ j ] ] = i; } for(int i=0; i<=maW; i++)Loc[i]=n+1; for(int i=n; i>0; i--) { int ww=w[i]; int R=n+1; for(int j=0; j<numofYZ[ ww ]; j++) R=min(R,Loc[ yinzi[ ww ][ j ] ]); wLR[i].R=R; G[R].push_back(i); for(int j=0; j < numofYZ[ ww ]; j++) Loc[ yinzi[ww][ j ] ]=i; } for(int i=0; i<m; i++) { Q[i].id=i; scanf("%d%d",&Q[i].L,&Q[i].R); } sort(Q,Q+m); int now=1; memset(C,0,sizeof(C)); for(int i=0; i<m; i++) { while(now<=Q[i].R) { for(int j=0; j<G[now].size(); j++) { int to=G[now][j]; add(to,-1); add(wLR[to].L,1); } add(now,1); add(wLR[now].L,-1); now++; } ans[Q[i].id]=sum(Q[i].R)-sum(Q[i].L-1); } for(int i=0; i<m; i++) printf("%d ",ans[i]); init(n); } return 0; }