题解CF1712E2【LCM Sum (hard version) 】

· · 题解

做法不太一样，发篇题解。

赛时居然切了 E1 没切 E2，可能大半夜脑子有点昏。

考虑计算出 \operatorname{lcm}(i,j,k) < i + j + k 的三元组数量，然后答案就是 C_{r-l+1}^3 减去这个数。

设 x = \operatorname{lcm}(i,j,k),i = \dfrac{x}{a},j = \dfrac{x}{b},k = \dfrac{x}{c}，那么有 a > b > c，而上面那个 \operatorname{lcm} 的条件就相当于\dfrac{1}{a} + \dfrac{1}{b} + \dfrac{1}{c} > 1。

要满足这个条件，可以分为 c=1 和 c \ne 1 两类。先讨论 c \ne 1 这一类。

如果 c \ge 3，那么 \dfrac{1}{a} < \dfrac{1}{b} < \dfrac{1}{c} \le \dfrac{1}{3}，所以有 \dfrac{1}{a} + \dfrac{1}{b} + \dfrac{1}{c} < \dfrac{1}{3} + \dfrac{1}{3} + \dfrac{1}{3} = 1，不符合条件，所以 c=2。

如果 b \ge 4，那么 \dfrac{1}{a} < \dfrac{1}{b} \le \dfrac{1}{4}，所以有 \dfrac{1}{a} + \dfrac{1}{b} + \dfrac{1}{c} < \dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{2} = 1，不符合条件，所以 b=3。

最后经尝试(?)，a \le 5。

所以刚才经过一大波初(xiao)中(xue)数(ao)学(shu)式的推导后，得出满足条件的 a,b,c 只有两组：(4,3,2) 和 (5,3,2)。对应到 i,j,k 的比例就是 3:4:6 和 6:10:15。

得出了这个比例后我们就可以很容易的求出有多少组满足的了。以第一个比例 3:4:6 为例，设 i = 3 \lambda,j = 4\lambda,k = 6\lambda。那么为了让 i,j,k 满足大小的限制，\lambda 的取值必须在 [\lceil \dfrac{l}{3} \rceil,\lfloor \dfrac{r}{6} \rfloor] 之间，而每一种取值都对应一组 i,j,k，所以直接 \max(0,\lfloor \dfrac{r}{6} \rfloor - \lceil \dfrac{l}{3} \rceil + 1) 即可。

同理，第二个比例算出来的公式是 \max(0,\lfloor \dfrac{r}{15} \rfloor - \lceil \dfrac{l}{6} \rceil + 1)。

重点是 c=1 这一类。这一类就相当于是 i,j 都是 k 的约数，那么设 cnt_i 表示在 [l,r] 中 i 的约数的数量（不包括 i），这一部分的答案就是 \sum\limits_{i=l}^rC_{cnt_i}^2。

可以反过来考虑，对于每个 i \in [l,r] ，将所有除 i 外的 i 的倍数的 cnt 值都加 1。

对于 E1，可以直接处理 cnt，然后就可以在 O(\sum r-l+1) 的时间解决。

对于 E2，我赛时完全没有想法，考虑了一下主席树，然后空间过大，弃了。

第二天白天准备补一下，在我就要点开 CF 官方题解的那一刻，我突然有了思路：这个直接离线不就行了！

然后推了一小会，通了。

还是前面那个做法，但是正着枚举 i 显得很棘手，所以考虑从 \max r 开始倒着枚举 i，同时更新对应位置的 cnt 值和 C_{cnt}^2 值。

发现一个 i 只会更新下标大于它的位置。所以对于一次询问 [l,r]，只需要在 l 更新完后查询区间 [l,r] 的 C_{cnt_i}^2 和即可，因为大于 r 的 i 的更新不会影响这个区间的值。

单点加区间求和是一个裸的树状数组，维护即可。

发现会更新 O(n \log n) 次，因为这是个调和级数。

最终复杂度 O(n \log^2 n)。

代码：

#include<cstdio>
#include<vector>
#define TY ll
#define MAXN 200002
#define MAXM 100002
#define debug if(1==1)
#define FOR(i,a,b) for(TY i=(a);i<=(b);++i)
#define fOR(i,a,b) for(TY i=(a);i<(b);++i)
#define ROF(i,a,b) for(TY i=(a);i>=(b);--i)
#define rOF(i,a,b) for(TY i=(a);i>(b);--i)
using namespace std;
typedef double db;
typedef long long ll;
const TY M=998244353;
typedef unsigned long long ull;
TY _abs(TY a){return a<0?-a:a;}
TY maxn(TY a,TY b){return a>b?a:b;}
TY minn(TY a,TY b){return a<b?a:b;}
TY gcd(TY a,TY b){return b?gcd(b,a%b):a;}
TY qp(TY a,TY b){TY ans=1;do{if(b&1)ans=ans*a%M;a=a*a%M;}while(b>>=1);return ans;}
char getc(){char ch=getchar();while(ch==' '||ch=='\n')ch=getchar();return ch;}
void prtcan(bool x,bool big){
    if(x){
        if(big)printf("YES\n");
        else printf("Yes\n");
    }else{
        if(big)printf("NO\n");
        else printf("No\n");
    }
}TY qr(){
    char ch=getchar();TY s=0,x=1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')x=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';return x*s;
}void qw(TY a,char ch){
    if(a<0){a=-a;putchar('-');}
    if(a>9)qw(a/10,0);putchar(a%10+'0');
    if(ch)putchar(ch);
}TY T=qr(),l,r,cnt[MAXN],tre[MAXN],ans[MAXM];vector<TY>id[MAXN],v[MAXN];
TY js(TY a){return a*(a-1)*(a-2)/6;}
TY len(TY l,TY r){return l<=r?r-l+1:0;}
inline void add(TY x,TY d){for(;x<MAXN;x+=x&-x)tre[x]+=d;}
TY ask(TY x){TY s=0;for(;x;x^=x&-x)s+=tre[x];return s;}
int main(){
    FOR(i,1,T){
        l=qr();r=qr();ans[i]=js(r-l+1);
        ans[i]-=len((l+2)/3,r/6);
        ans[i]-=len((l+5)/6,r/15);//c不等于1的情况
        id[l].push_back(i);v[l].push_back(r);
    }ROF(i,MAXN-1,1){
        for(TY j=i<<1;j<MAXN;j+=i)add(j,cnt[j]++);//tre维护C(cnt,2)的树状数组
        fOR(j,0,id[i].size())ans[id[i][j]]-=ask(v[i][j])-ask(i-1);//c=1的情况考虑
    }FOR(i,1,T)qw(ans[i],'\n');
    return 0;
}