题目大意：
给出一个长度为n的数列a1,a2,a3,...,an，以及m组询问(li,ri,ki)，求区间[li,ri]中有多少数在该区间中的出现次数与ki互质。
思路：
莫队。
f[i]记录数字i出现的次数，用一个链表记录f[i]的出现次数。
一开始没用链表，用map，在SimpleOJ上随便A，但是在LOJ上只有50分。
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int N=,M=;
int a[N],f[N],ans[M],block;
struct Question {
int l,r,k,id;
bool operator < (const Question &another) const {
return l/block==another.l/block?r/block<another.r/block:l/block<another.l/block;
}
};
Question q[M];
struct List {
int val[N],last[N],next[N],end;
int &operator [] (const int &p) {
return val[p];
}
void insert(const int &x) {
next[end]=x;
last[x]=end;
end=x;
}
void erase(const int &x) {
if(x==end) end=last[x];
next[last[x]]=next[x];
last[next[x]]=last[x];
val[x]=last[x]=next[x]=;
}
};
List list;
inline void insert(const int &x) {
if(f[x]&&!--list[f[x]]) list.erase(f[x]);
if(!list[++f[x]]) list.insert(f[x]);
list[f[x]]++;
}
inline void erase(const int &x) {
if(!--list[f[x]]) list.erase(f[x]);
if(--f[x]) {
if(!list[f[x]]) list.insert(f[x]);
list[f[x]]++;
}
}
int gcd(const int &a,const int &b) {
return b?gcd(b,a%b):a;
}
int main() {
const int n=getint(),m=getint();
block=sqrt(m);
for(register int i=;i<=n;i++) a[i]=getint();
for(register int i=;i<m;i++) {
q[i]=(Question){getint(),getint(),getint(),i};
}
std::sort(&q[],&q[m]);
for(register int i=,l=,r=;i<m;i++) {
while(l>q[i].l) insert(a[--l]);
while(r<q[i].r) insert(a[++r]);
while(l<q[i].l) erase(a[l++]);
while(r>q[i].r) erase(a[r--]);
for(register int j=list.end;j;j=list.last[j]) {
if(gcd(j,q[i].k)==) ans[q[i].id]+=list[j];
}
}
for(register int i=;i<m;i++) {
printf("%d\n",ans[i]);
}
return ;
}