LCM Sum[数论+树状数组]

#pragma GCC optimize(2)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
struct sq
{
	int l,r,id;
}q[100005];//存储查询
struct poi
{
	int x,y,cnt;
}a[10000005];//存储(x,y)之间y的因子数，也就是固定x,y能组成的坏三元组数
int sz[200005],tot,bit[200005];
ll ans[200005];
vector<int>fac[200005];//存储因子
void pre()
{
	for(int i=1;i<=2e5;i++)
	{
		for(int j=2;j*i<=2e5;j++)
		{
			sz[i*j]++;
			fac[i*j].push_back(i);
		}
	}
	for(int i=1;i<=2e5;i++)
	{
		for(int j=0;j<(ll)fac[i].size()-1;j++)
		{
			a[++tot].x=fac[i][j];
			a[tot].y=i;
			a[tot].cnt=sz[i]-1;//记得不包括x,y所以要-1
			sz[i]--;
		}
	}
	//按照右端点排序
	sort(a+1,a+1+tot,[](poi x,poi y)->bool{return x.y==y.y?x.x<y.x:x.y<y.y;});
}
//下面是树状数组
inline int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int k)
{
	while(x<=2e5)
	{
		bit[x]+=k;
		x+=lowbit(x);
	}
}
ll ask(int x)
{
	ll sum=0;
	while(x>0)
	{
		sum+=bit[x];
		x-=lowbit(x);
	}
	return sum;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pre();
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		cin>>q[i].l>>q[i].r;
		//先算好ans
		ans[i]=1LL*(q[i].r-q[i].l+1)*(q[i].r-q[i].l)/2*(q[i].r-q[i].l-1)/3;
		//处理两种2k的情况
		ans[i]-=max((ll)0,(ll)q[i].r/6-(q[i].l-1)/3);
		ans[i]-=max((ll)0,(ll)q[i].r/15-(q[i].l-1)/6);
		q[i].id=i;
	}
	//将询问也按照右端点排序
	sort(q+1,q+1+t,[](sq x,sq y)->bool{return x.r<y.r;});
	int lt=1;
	for(int i=1;i<=t;i++)
	{
		//把当前对该区间可能有贡献的先加上
		while(a[lt].y<=q[i].r&&lt<=tot)
		{
			//我们之前已经计算了对于固定的右节点，每个左节点的贡献值是多少，
			//累加到对应左节点上，此时左节点的值代表R为q[i].r时，该节点能贡献的坏二元组数
			//那么前缀和就是从1-R的坏二元组数之和了。
			//似乎树状数组经典的按照第二维有序，那么就按照无序的另一维来进行添加
			add(a[lt].x,a[lt].cnt);
			lt++;
		}
		//类似前缀和作差
		ans[q[i].id]-=(ask(q[i].r)-ask(q[i].l-1));
	}
	for(int i=1;i<=t;i++)
		cout<<ans[i]<<'\n';
	return 0;
}