记录编号	377133	评测结果	AAAAAAAAAAA
题目名称	[河南省队2016]HH树	最终得分	100
用户昵称	苦读依旧	是否通过	通过
代码语言	C++	运行时间	8.582 s
提交时间	2017-02-28 20:29:53	内存使用	4.26 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
//#define int ll
struct q{
int l,r;
int id;
} t[51000];
int a[51100];
vector<int> c[51000];
vector<int> ct[51000];
vector<int> g[51000];
int cnt[52000];
ll ans[51000];
ll hg[51000];
int prime[51000];
bool bl[51000];
int pos[51000];
int tt=0;
ll sum=0;
int block=0;
int size=0;
int n,Q; 
bool cmp(const q a,const q b)
{
	if(pos[a.l]<pos[b.l]) return 1;
	else if(pos[a.l]==pos[b.l]) return a.r<b.r;
	return 0;
}
int power(int a,int b)
{
	int r=1; int w=a;
	while(b) {
		if(b&1) r=r*w;
		w=w*w;
		b>>=1; 
	}
	return r;
}
void update(int x,int p)
{
//	cout<<"         "<<x<<endl;
	for(int i=0;i<c[a[x]].size();++i) {
		int vv=c[a[x]][i];
		int num=ct[a[x]][i];
//		cout<<num<<endl;
		if(p>0) sum+=power(-1,num+1)*p*(ll)hg[vv];
		hg[vv]+=p;
		if(p<0) sum+=power(-1,num+1)*p*(ll)hg[vv];
	}
}
void solve()
{
	int l=1; int r=1; sum=0;
	for(int i=0;i<c[a[1]].size();++i) {
		int vv=c[a[1]][i];
		hg[vv]++;
	}
	for(int i=1;i<=Q;++i) {
//		cout<<"/////////////////////////"<<endl;
//		cout<<l<<"       "<<r<<endl;
//		cout<<t[i].l<<"    "<<t[i].r<<endl;
		while(r<t[i].r) update(++r,1);
		while(l>t[i].l) update(--l,1);
		while(r>t[i].r) update(r--,-1);
		while(l<t[i].l) update(l++,-1);
		ans[t[i].id]=(ll)(r-l+1)*(ll)(r-l)/(ll)2-sum;
//		cout<<"aa "<<sum<<endl;
	}
}
main()
{
	freopen("hhtree.in","r",stdin);
	freopen("hhtree.out","w",stdout);
	for(int i=2;i<=50000;++i) {
		if(!bl[i]) prime[++tt]=i;
		for(int j=1;j<=tt;++j) {
			if(prime[j]*i>50000) break;
			bl[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
	for(int i=1;i<=((1<<6)-1);++i) {
		int tmp=i;
		while(tmp) {
			tmp=tmp&(tmp-1);
			cnt[i]++;
		}
	}
	scanf("%d%d",&n,&Q);
	size=sqrt(n); block=(n-1)/size+1;
	for(int i=1;i<=n;++i) {
		int x; scanf("%d",&x); a[i]=x;
		pos[i]=(i-1)/size+1;
//		L[pos[i]]=R[pos[i]-1]+1; R[pos[i]]=i;
		int d=sqrt(x); int w=x;
		if(g[x].size()) continue;
		for(int j=1;j<=tt;++j) {
			if(prime[j]>d||w<prime[j]) break;
			if(w%prime[j]==0) g[x].push_back(prime[j]);
			while(w%prime[j]==0) w/=prime[j];
		}
		if(w!=1) g[x].push_back(w);
//		cout<<x<<"    "<<a[i]<<"    "<<g[x].size()<<endl;
	}
	for(int i=1;i<=n;++i) {
		if(!c[a[i]].size())
		for(int j=1;j<=(1<<(g[a[i]].size()))-1;++j) {
//			cout<<"\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"<<endl;
//			cout<<a[i]<<"     "<<g[a[i]].size()<<endl;
			int tmp=1;
			for(int k=0;k<g[a[i]].size();++k) {
				int vv=g[a[i]][k];
				tmp*=power(vv,((j&(1<<k))>>k));
//				cout<<tmp<<"    "<<g[a[i]].size()<<"       "<<((j&(1<<k))>>k)<<endl;
			}
			c[a[i]].push_back(tmp);
			ct[a[i]].push_back(cnt[j]);
		}
	}
	for(int i=1;i<=Q;++i) {
		int x,y; scanf("%d%d",&x,&y);
		t[i].l=x; t[i].r=y;
		t[i].id=i;
	}
	sort(t+1,t+Q+1,cmp);
	solve();
	for(int i=1;i<=Q;++i) printf("%d\n",ans[i]);
	return 0;
}