题意：给你一个长度数列，再给你m个询问（一个区间），问你在这个区间里面有多少个数与其他的数都互质。
解题思路：你看这种类型的题目都可以肯定这是 离线+树状数组（线段树）。主要就是他的更新信息。这里我的处理是先把1-200000（每个数的范围）数里面所有的质因子求出来。然后从后往前遍历数组。会出现以下几种情况
1.a[k]的质因子在后面出现过而【更新标记】 和【被更新标记】 都为假
2.a[k]的质因子在后面出现过的那个位置 I 【更新标记】为 真 。
3.a[k]的质因子在后面出现过且那个位置 I 【被更新标记】 为真 。
如果只出现 1 这种情况，那么这个位置 +1，【更新标记】 变为真；
如果只出现 2 这种情况， 那么对这个位置不更新。
如果出现 3 这种情况， 那么 I 的被更新位置 -1 ，I位置 +1 ，且 I的被更新标记变为假。
在这个过程中，a[k]的所有质因子的 最新位置 都变为K ，再找到到离 a【K】 最近的和它 不互质的数 a【X】 把K的 【被更新标记】变为 X，再在X位置 +1
（上面所有的操作都是为了使得记数不 错误）
最后的答案就是 区间内数的个数 - 区间求的和。
解题代码：
1 // File Name: c.cpp 2 // Author: darkdream 3 // Created Time: 2014年05月07日 星期三 17时07分23秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 25 using namespace std; 26 #define MAXN 200005 27 28 29 int a[MAXN]; 30 struct lr{ 31 int l,r,num; 32 }q[MAXN]; 33 int cmp(lr a, lr b) 34 { 35 return a.l > b.l; 36 } 37 int tree[MAXN]; 38 int lowbit(int x) 39 { 40 return x&(-x); 41 } 42 int getsum(int l,int k) 43 { 44 int sum = 0 ; 45 while(k >= l ) 46 { 47 sum += tree[k]; 48 k -= lowbit(k); 49 } 50 return sum ; 51 } 52 int n; 53 int hs[MAXN]; 54 void update(int k ,int v ) 55 { 56 // printf("%d ",k); 57 while(k <= n) 58 { 59 tree[k] += v; 60 k += lowbit(k); 61 } 62 63 } 64 int ans[MAXN]; 65 int prime[MAXN][20]; 66 int num[MAXN]; 67 int last[MAXN]; 68 void solve(){ 69 memset(num,0,sizeof(num)); 70 memset(hs,0,sizeof(hs)); 71 for(int i = 2 ;i <= 200000;i ++) 72 { 73 if(hs[i] == 0 ) 74 { 75 int k = i; 76 while(k <= 200000) 77 { 78 num[k] ++ ; 79 prime[k][num[k]] = i ; 80 hs[k] = 1; 81 k += i ; 82 } 83 } 84 } 85 } 86 int isupdate[MAXN]; 87 int cmp1(int a, int b) 88 { 89 return a < b ; 90 } 91 int main(){ 92 //freopen("intpu.in","r",stdin); 93 int m ; 94 solve(); 95 //printf("*** "); 96 while(scanf("%d %d", &n,&m) != EOF) 97 { 98 if(n == 0 && m == 0 ) 99 break; 100 memset(tree,0,sizeof(tree)); 101 memset(q,0,sizeof(q)); 102 103 104 for(int i = 1;i <= n;i ++) 105 scanf("%d",&a[i]); 106 for(int i = 1;i <= m;i ++) 107 { 108 scanf("%d %d",&q[i].l,&q[i].r); 109 q[i].num = i; 110 } 111 sort(q+1,q+m+1,cmp); 112 113 int p = 1; 114 memset(hs,0,sizeof(hs)); 115 memset(last,0,sizeof(last)); 116 memset(isupdate,0,sizeof(isupdate)); 117 //memset(q,0,sizeof(q)); 118 for(int i = n;i >= 1 ;--i) 119 { 120 int ta[20]; 121 int tanum = 0 ; 122 memset(ta,0,sizeof(ta)); 123 for(int j = 1; j <= num[a[i]]; ++j ) 124 { 125 int temp = prime[a[i]][j]; 126 if(hs[temp]) 127 { 128 tanum ++ ; 129 ta[tanum] = hs[temp]; 130 } 131 hs[temp] = i ; 132 } 133 if(tanum) 134 { 135 sort(ta+1,ta+tanum+1,cmp1); 136 int min = ta[1]; 137 for(int j = 1;j <= tanum;j ++) 138 { 139 if(ta[j]!= ta[j-1]) 140 { 141 if(last[ta[j]]) 142 { 143 update(last[ta[j]],-1); 144 update(ta[j],1); 145 last[ta[j]] = 0 ; 146 }else { 147 if(!isupdate[ta[j]]) 148 { 149 update(ta[j],1); 150 isupdate[ta[j]] = 1 ; 151 } 152 } 153 if(ta[j] < min) 154 min = ta[j]; 155 } 156 } 157 update(min,1); 158 isupdate[min] = 1; 159 last[i] = min; 160 isupdate[i] = 1; 161 162 } 163 while(q[p].l == i ) 164 { 165 ans[q[p].num] = (q[p].r - q[p].l +1) - getsum(q[p].l,q[p].r); 166 p++; 167 } 168 } 169 for(int i = 1;i <= m;++i) 170 printf("%d ",ans[i]); 171 } 172 return 0; 173 }