Link

CF1891 D Suspicious logarithms

Question

我们设 \(y=f(x)\) 表示最大的 \(y\) 满足 \(2^y \le x\)

设 \(z=g(x)\) 表示最大的 \(z\) 满足 \(f(x) ^z \le x\)

求

\[\sum\limits_{i=L_i}^{R_i}\ g(i) \]

Solution

我们列出一些数，可以发现一些规律，就是一大段数的 \(f(x)\) 和 \(g(x)\) 是相同的

也就是说 \(f(x),g(x)\) 的个数是 \(\log\) 级别的

所以，我们可以一起求出一块的 \(g(x)\)

这里需要一个前缀和的思想：\(s_g(L,R)=s_g(1,R)-s_g(1,L-1)\)

所以我们定义 \(get_1(x)\) 表示从 \(1\) 到 \(x\) \(g()\) 的求和

我们把区间分成几块，第 \(i\) 区间是 \([2^{i-1},2^i-1]\)

在这个区间里面的 \(f()\) 都是相同的是 \(i-1\)

然后我们对这个区间里面的 \(g()\) 求和

也是一块一块的求，\(g()^i\) 增长的很快，一会儿就爆出区间了

但是我们发现这样的复杂度 \(O(n log^2 n)\)

思考如何优化，对于相同的一段区间，我们反复求了很多次

用数组提前记下来预处理一下就好了

Code

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<windows.h>

#define int __int128
using namespace std;
const int MAX_X=1e18,TT=1e9+7;
int F[65];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void print(int x){
    stack<int> p;
    do{p.push(x%10);x/=10;}while(x);
    while(!p.empty()) putchar(p.top()+'0'),p.pop();
    putchar('\n');
}
int get_2(int r,int p){
    if(r<=1||p==1) return 0;
    int pn=1,ret=0;
    for(int i=1;;i++){
        pn=pn*p;
        if(pn*p>r) { //如果 p^(n+1) > r 那么最后一块加上 n
            ret=(ret+(r-(pn-1))*i)%TT;
            return ret;
        }
        ret=(ret+((pn*p-1)-(pn-1))*i)%TT; // [p^n,p^(n+1)-1]
    }
}
int get_1(int now){
    int ans=0;
    int R=0,L;
    for(int i=1;;i++){
        R=(1ll<<i)-1,L=(1ll<<i-1);
        R=min(R,now);
        if(R==now){
            int sum_L=get_2(L-1,i-1);
            int sum_R=get_2(R,i-1);
            ans=(F[i-1]+sum_R-sum_L+TT)%TT;
            break;
        }
        // if(R==now) break;
    }
    return ans;
}
inline void init(){
    int ans=0;
    int R=0,L;
    for(int i=1;;i++){
        R=(1ll<<i)-1,L=(1ll<<i-1);
        int sum_L=get_2(L-1,i-1);
        int sum_R=get_2(R,i-1);
        ans=(ans+sum_R-sum_L+TT)%TT;
        F[i]=ans;
        if(R>MAX_X) break;
    }
    return ;

}
signed main(){
    int T=read();
    init();
    while(T--){
        int L=read(),R=read();
        print((get_1(R)-get_1(L-1)+TT)%TT);
    }
    // printf("%d\n",clock());
    return 0;
}

JZTXT

CF1891 D Suspicious logarithms 题解

Link

Question

Solution

Code