商店(分块+二分)

题目描述

从前有一个奇怪的商店，一共售卖k种物品，第i种物品的初始价格为i。
但是这商店有个很奇怪的规矩，就是你每次购买一样物品之后，这种物品的价格都会在当前基础上翻一倍。
现在我们想要用最少的钱从里面买n样物品，不限购买的物品种数和每种物品购买的次数，请求出若这样做，所买到的最贵的物品的价格，由于这个数字可能过大，你只需要输出其模1000000007=10^9+7的结果即可。

输入

每个测试点第一行一个整数T，表示数据组数。
接下来T行，每行两个正整数n,k。

输出

T行，第i行表示第i组数据的答案。

样例输入 Copy

5
3 1
3 2
5 3
1000000000 1
987654321 876543210

样例输出 Copy

提示

对于100%的数据，1≤T≤2000，1≤n,k≤10^9。

分两种情况;

1.答案小于等于k

2.答案大于k

对于第一种情况，直接二分答案，对于每一个二分的答案x,计算，这部分采用分块加速即可

对于第二种情况，首先算出价格为k时所能买到的物品数量为mx,那么剩余需要买的数量为num1=n-mx,因为1~n这些数*2的比n大的数在[n+1,2*n]这个范围里直接对应，并且这个[n+1,2*n]出现的数为n个数，对于[2*n+1,4*n]这个范围也是如此，并且每一个数之间的大小关系不发生变化，所以，我们只要求出有num1/n个这样的完整区间，然后剩下的num1%n在[n/2+1,n]区间中找即可。

复杂度为(t*sqrt(k)*log(k))

update:至于为啥在[n/2+1,n]这个区间找是因为如果在[1,n/2]这个区间，里面任何数的2倍还是在[1,n]之间

/**/
#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
 
typedef long long LL;
using namespace std;
 
const long long mod = 1e9 + 7;
 
int t, n, k;
LL mx;
 
int check(int x){
    LL ans = 0;
    for (int i = 1, j; i <= x; i = j + 1){
        j = x / (x / i);
        ans += ((LL)std::log2(1.0 * x / i) + 1) * (j - i + 1);
    }
    mx = max(mx, ans);
    return ans >= k;
}

int get(int x){
    LL ans = 0;
    for (int i = 1, j; i <= x; i = j + 1){
        j = x / (x / i);
        ans += ((LL)std::log2(1.0 * x / i) + 1) * (j - i + 1);
    }
    return ans;
}

int check1(int x, int num){
    LL ans = 0;
    for (int i = 1, j; i <= x; i = j + 1){
        j = x / (x / i);
        ans += ((LL)std::log2(1.0 * x / i) + 1) * (j - i + 1);
    }
    return ans >= num;
}
 
LL poww(LL x, LL num){
    LL res = 1;
    while(num){
        if(num & 1) res = res * x % mod;
        x = x * x % mod;
        num >>= 1;
    }
    return res;
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    scanf("%d", &t);
    while(t--){
        mx = 0;
        scanf("%d %d", &k, &n);
        if(!check(n)){
            int num = get(n >> 1);
            int num1 = k - mx;
            int num2 = num1 / n;
            num1 %= n;
            if(num1 == 0) num1 = n, num2--;
            int l = (n >> 1), r = n, ans = n;
            while(l <= r){
            	int mid = (l + r) >> 1;
            	if(check1(mid, num1 + num)) ans = mid, r = mid - 1;
            	else l = mid + 1;
            }
            printf("%lld\n", (ans << 1) * poww(2, num2) % mod);
            continue;
        }
        int l = 0, r = n, ans = n;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(check(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        printf("%d\n", ans);
    }
 
    return 0;
}
/*
6
3 1
3 2
5 3
1000000000 1
987654321 876543210
6 3
*/