CF1891D Suspicious logarithms 题解

· · 题解

CF1891D Suspicious logarithms 题解

题目描述

记 f(x) = \lfloor \log_2(x) \rfloor,g(x) = \lfloor \log_{f(x)}x\rfloor，q 组询问，每个询问给定 l,r，求 \sum \limits_{i=l}^r g(i)。答案对 10^9+7 取模。q\le 10^5,l,r\le10^{18}。

解决方案

不难发现，f(x) 的取值并不多，只有 60 种，不妨先枚举 f(x)，在计算贡献。显然，它的取值范围是 2^{f(x)}\sim 2^{f(x)+1}-1。而 g(x) 的取值也不多，因为 log_{f(x)}x 显然不会很大，打表发现最多只有 10 种，再次枚举 g(x)，每个数的贡献为 g(x)，范围是 l\sim r，2^{f(x)}\sim 2^{f(x)+1}-1，f(x)^{g(x)}\sim f(x)^{g(x)+1}-1 三条线段的交集，记长度为 len，则对答案的总贡献为 len\times g(x)。这样计算周期数量为 600n，注意有的地方要用__int128。实测加了快读后比 O(q\log^2r) 要快一些。

代码

#include<bits/stdc++.h>
using namespace std;typedef __int128 i128;typedef long long ll;
const ll MOD=1e9+7;ll Q,l,r,L,R,fx,ans,p2[102];char c;
inline ll lenth(ll X1,ll X2,ll Y1,ll Y2,ll Z1,ll Z2){
    return max(min(min(X2,Y2),Z2)-max(max(X1,Y1),Z1)+1,(ll)0);
}
inline void read(ll &x){
    x=0,c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
inline void write(ll x){
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
int main(){
    read(Q),p2[0]=1;
    for(int i=1;i<=60;i++)p2[i]=p2[i-1]*2;
    while(Q--){
        read(l),read(r),fx=1,ans=0;
        for(int i=1;i<=60;i++){
            fx=i;
            for(int j=1;j<=10;j++){
                L=fx,fx=min((i128)fx*i,(i128)1e18+1),R=fx-1,
                (ans+=j*lenth(L,R,p2[i],p2[i+1]-1,l,r)%MOD)%=MOD;
                if(fx>p2[i+1]-1||fx>r)break;
            }
        }
        write(ans),putchar('\n');
    }
    return 0;
}