本文主要是介绍D. Suspicious logarithms Codeforces Round 907 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem - D - Codeforces
题目大意：令f(X)=log2（x）向下取整，g(x)=logf(x)x，有q次询问，求在lr区间内的所有数的g(x)之和
1<=q<=1e5；4<=l<=r<=1e18
思路：我们打个表发现，在一个2的幂的长度内，g(x)最多有两个不同值，求都是连续分布的，例如[4,7]都是2[8.15]内8是3，[9,15]内是2，这样我们可以枚举每个长度为2的幂的区间，设2的指数为i当前区间[l,r]即为[2的i次方，2的i+1次方-1]，我们枚举找到一个最大的i的幂now使其小于等于l，同时这个幂也就是g(x)的值即为cnt。
这时有两种情况，g(x)+1的地方也就是now*i有可能在当前枚举的区间外，这个区间的贡献就是(r-l+1)*cnt，另一种情况就是g(x)+1的地方在区间内，这个地方已知是now*i，那么这个区间的贡献就是(now*i-1-l+1)*cnt+(r-now*i+1)*(cnt+1)，这样枚举i直到2的i次方大于上限R，就能得到g(x)x属于1到R的答案，我们令R=询问的r和询问的l-1，分别求出相减即可。
//#include <bits/stdc++.h>
#include<__msvc_all_public_headers.hpp>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll MOD = 1e9 + 7;
int a[N];
ll cal(ll x)
{ll ans = 0;for (ll i = 2; (1ll << i) <= x; i++){//枚举2的i次方ll l = 1ll << i;//2的i次方ll r = min(x, (1ll << i + 1) - 1);//枚举2的i+1次方-1ll cnt = 0;//f(l)的z次方ll now = 1;//x=l时的zwhile (now * i <= l){//找到最大的小于等于l的i的幂cnt++;now *= i;}if (now * i > r){//整个区间g(x)都是一个数ans = (ans + (r - l + 1) % MOD * cnt % MOD) % MOD;}else{//前面是一个数，后面是那个数+1ans = (ans + (r - now * i + 1) % MOD * (cnt + 1) % MOD + (now * i - l) % MOD * cnt % MOD) % MOD;}}return ans;
}
void solve()
{ll l, r;cin >> l >> r;cout << (cal(r) - cal(l - 1)+MOD) % MOD << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}}
这篇关于D. Suspicious logarithms Codeforces Round 907 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
