记录编号	417057	评测结果	AAAAAAAAAAA
题目名称	[河南省队2016]HH树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.632 s
提交时间	2017-06-23 22:15:49	内存使用	14.46 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=5e4+10;
int n,q,blo,a[N],u[N],p[N],F[N],now,cnt;
bool isp[N];
int que[N][65],num[N];
struct opt{int l,r,id;}Q[N];
int ans[N];
bool cmp(const opt &x,const opt &y){
	return x.l/blo==y.l/blo?x.r<y.r:x.l/blo<y.l/blo; 
}
void push(int x){
	for (register int i=num[x],d;i;--i){
		d=que[x][i];
		now+=F[d]*u[d];
		F[d]++;
	}
}
void del(int x){
	for (register int i=num[x],d;i;--i){
		d=que[x][i];
		F[d]--;
		now-=F[d]*u[d];
	}
}
void init(){
	u[1]=1;
	for (int i=2;i<=5e4;i++){
		if (!isp[i]) isp[i]=1,p[++cnt]=i,u[i]=-1;
		for (int j=1;j<=cnt&&i*p[j]<=5e4;j++){
			int x=i*p[j];isp[x]=1;
			if (i%p[j]) u[x]=-u[i];
			else{u[x]=0;break;}
		}
	}
	for (int i=1;i<=5e4;i++)
	for (int j=i;j<=5e4;j+=i)
		if (u[i]) que[j][++num[j]]=i;
}
int main()
{
	freopen("hhtree.in","r",stdin);
	freopen("hhtree.out","w",stdout);
	init();
	scanf("%d%d",&n,&q);
	blo=sqrt(n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=q;i++)
		scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+q+1,cmp);
	int l=Q[1].l,r=l-1;
	for (int i=1;i<=q;i++){
		while (r<Q[i].r) push(a[++r]);
		while (l>Q[i].l) push(a[--l]);
		while (r>Q[i].r) del(a[r--]);
		while (l<Q[i].l) del(a[l++]);
		ans[Q[i].id]=now;
	}
	for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}