给一个区间[L,R]，询问有多少三元组(i,j,k)满足L=<i<j<k<=r且lcm(i,j,k)>=i+j+k.
正难则反。我们可以考虑它的补集。
lcm<i+j+k,然后是i+j+k<3*k
所以lcm<3k,又因为k是lcm的因数，所以lcm=k或者2k。
那么答案变成了求L,R里lcm=k和2k的三元组的数目
如果lcm=k说明i,j都是k的因数，等于2k的手算推出来只有(3,4,6)和(6,10,15)两个及他们的倍数。
总共有(r-l+1)*(r-l)/2*(r-l-1)/3种，减去上述两种即可。
E1的简单版本数据范围小，枚举可以过，E2数据过大，由于我目前还不会CDQ分治，最后选择的树状数组。
要求i∈L,R里Σfac(i),我们可以看成一个前缀和,因为R<=2e5所以完全可以建立一个树状数组。用一个数组处理好(i,k)之间k的因子j的个数(i也是k的因子)，就是固定i,k后的坏三元组的数目。按照右端点升序排列(n sqrt(n)数量级)
把查询存起来，按照右端点升序。每次查询之前加入右端点小于等于查询右端点的数，那么此时的前缀和ask(c)就是1-c对1-R里坏三元组的贡献。
最后按照前缀和相减得结果即可
查看代码
#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&<<=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;
}