碎碎念
今天补了两题，但是都补了但没完全补
一道是1716F，整道题就考一个用第二类斯特林数去化简一个式子
我就按照题解化了一遍，也不能保证自己有多懂，就不写出来了
另一道题的核心部分是自己推的，但是有个重要但没那么重要的结论是看题解的呜呜呜
CF1712E LCM Sum
给你l和r，询问有多少组l<=i<j<k<=r满足lcm(i,j,k)>=i+j+k
多组数据，T<=1e5,l<r<=2e5
solution
首先考虑对最大数k进行统计方案数，有lcm(i,j,k)一定是k的倍数
同时只有当lcm(i,j,k)是k的1或2倍时才有可能不满足条件
对于lcm(i,j,k)=2k，有结论i,j,k一定是(3,4,6)或(6,10,15)的倍数才不满足条件（不会证）
update：又爆肝了一会终于会证了，我们发现不满足条件的i,j一定满足i,j都是2k的因数且i+j>k
而2k的因数都可以表示为形如2k/d的形式，那么令i=2k/a，j=2k/b，我们有b<a且3<=b<4即b=3
此时2k/a>k/3即a<6，所以a=4或5，a=4时为(3,4,6)，a=5时为(6,10,15)
对于lca(i,j,k)=k，一定不满足条件，而对于k来说(i,j,k)的方案数就是从k的约数中取两个
现在问题就转化成了一个有限制的区间求和问题
对于一个节点，我们需要维护的信息是这个点在[l,r]范围内约数的个数
而这个问题我们可以通过对l进行排序来离线进行处理
对于一个数x，会对n/x个数产生贡献，而对于所有的x，n/x求和之后是调和级数即n*ln(n)
所以我们会在线段树上进行n*ln(n)次单点修改，总复杂度n*ln(n)*log(n)，可以通过本题
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define N 200000
using namespace std;
ll C(int x,int y)
{
ll z=1;
for(int i=1;i<=y;i++)
z=z*(x-i+1)/i;
return z;
}
struct tree{ll ans;int c;}tr[(N+10)<<2];
#define ls (nw<<1)
#define rs (ls+1)
#define mid (l+r>>1)
void modify(int nw,int l,int r,int q,int x)
{
if(l==r)
{
tr[nw].c+=x;
tr[nw].ans=1ll*tr[nw].c*(tr[nw].c-1)/2;
return;
}
if(q<=mid)
modify(ls,l,mid,q,x);
else modify(rs,mid+1,r,q,x);
tr[nw].ans=tr[ls].ans+tr[rs].ans;
}
ll query(int nw,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return tr[nw].ans;
if(qr<=mid)return query(ls,l,mid,ql,qr);
if(ql>mid)return query(rs,mid+1,r,ql,qr);
return query(ls,l,mid,ql,qr)+query(rs,mid+1,r,ql,qr);
}
struct node{int l,r,id;}o[(N>>1)+10];
bool cmp(node x,node y){return x.l==y.l?x.id<y.id:x.l>y.l;}
int n;ll ans[(N>>1)+10];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++)
cin >> o[i].l >> o[i].r,o[i].id=i;
sort(o+1,o+n+1,cmp);
for(int i=1,lst=N;i<=n;i++)
{
while(lst>=o[i].l)
{
//add lst
for(int j=lst+lst;j<=N;j+=lst)
modify(1,1,N,j,1);
lst--;
}
int l=o[i].l,r=o[i].r;
ans[o[i].id]=C(r-l+1,3)-query(1,1,N,l+2,r)-max(0,(r/6-(l+2)/3+1))-max(0,(r/15-(l+5)/6+1));
}
for(int i=1;i<=n;i++)
cout << ans[i] << endl;
return 0;
}
Comments NOTHING