可以说每个带多样例的有$10^{18}$的超大空间单点询问都是有纯粹的数学逻辑和策略的。

题目目的是这样的

（不讲题意了，作为学习英文的一种必要训练）

给定$n$，$k$，记一个已完成的量为$x$，初始值$x_0=1$，每次倍增$x$，当倍增数量超过$2k$时，就每次只递增$k$个。

根据题意，首先，若$n$本身是$2$的幂，那么显然只要$k\geq n$，那么最终的操作次数就是$\log_2 n$。而除此之外不满$2$的幂的，显然是向上补，即多出一个都要加一次。

故，这个方面的结果就是$\left\lceil \log _2(n)\right\rceil$。

然后是，关于$k$的倍增情况，在$x$倍增的基础上，需要$k$的量也是同时倍增的。因此，和次数有关的关系就是一个 $2^p \le k$ 但已倍增的量相当于多乘一个$2$（一开始用一条线就传完两台机），故考虑这样的结果：

已完成的量为$2^{q} \le 2 k$。其实两者的关系指数上就差一，值的关系就差个两倍。

要求$2^p \le k$的$p$

这里用一种概念来表示分别为$\text{lowbit}$和$\text{highbit}$，但由于位和值的关系，我一般需要对应位上的值时，在后面补上一个'v'，即$\text{lowbitv}$等。

根据这些描述，一般来说可以知道$p=\left\lfloor \log _2(k)\right\rfloor$，但是求$\log _2(k)$很可能会发生浮点问题，对于该题来说，即使你使用long double相关的运算也无法保证算对。对于这种问题，提出了一系列基于进制的函数概念，首先，low和high其实就分别对应于最低与最高位的位置。一般定义-bit中正是将其定义为其仅保留最高或最低位的值的运算。

按我这里的概念就是说：

$$2^p=\text{highbitv}\left(k\right)$$

当然，要算已完成的，就是算$$\text{highbitv}\left(2k\right)$$

关于剩下的部分，如果$k$不够倍增了，那么只能按$k$递增处理，根据前面说的，多出一个都要增加次数，所以是向上取整的过程，加上已经倍增了的数量可得：

$$\left\lceil \frac{n-\text{highbitv}(2k)}{k}\right\rceil+p+1 $$

由于这个情况是倍增尽了的，所以说，既是倍增了$p+1$次，也是要求$n-\text{highbitv}(2k)$故完全可以不用考虑$p$，而是求$p+1=\log_2(2k)$以及$2^{p+1}=\text{highbitv}(2k)$。

Ext

公式一：

$$\left\lceil \frac{a}{b}\right\rceil =\left\lfloor \frac{a+b-1}{b}\right\rfloor $$

公式二：

$$\left\lceil \log _2(n)\right\rceil =\left\lfloor \log _2(2 n-1)\right\rfloor $$

这两个公式是让计算机真正能算的一个关键步骤，由于$\log _2(x)$在非$2$的幂中未必正确，因此需要确定整数级的算法计算，这就是$\text{highbitv}$，其实质就是算$\left\lfloor \log _2(k)\right\rfloor$，所以说，说到带high、low的实质是确定整数或进制运算去求某个本意上是实数函数的数学对象，他们都是进制函数。

使用公式一：

$$\left\lceil \frac{n-\text{highbitv}(2 k)}{k}\right\rceil+p+1 $$

等价于算：

(n - (1ull << (p + 1)) + k - 1) / k + p + 1

根据公式二，可以预先算出两个值，一个是 $\text{highbitv}(2 n-1)$ 记为$k_1$一个是 $\text{highbitv}(2 k)$ 记为$k_2$。

根据比较关系，当$k_1\le k_2$时，应输出$\log_2\left(k_1\right)$（考虑储存数制即可）

否则，输出(n - k2 + k - 1) / k + (ull)log2(k2)

Ext2

$\text{highbitv}$的算法：

一：一位位数，从最大位开始（如0x8000000000000000ull）可以只用1去位与（单个&运算符），第一个非零的即是。运算量为前导零的个数的四倍加三。

二：一位位数，但从小到大，会比较麻烦，首先初始值为-1（对应于无符号的所有位都为1），一直左移，直到位与（&）为0的前一个位。运算量为highbitv本身的四倍

三：使用lowbitv(x)==x&(-x)==x&(x-1)。逐位消除，运算量为二进制为1的个数的四倍。

这里举例方法三的代码：

ull hbv(ull x) {
    ull y;
    do { y = x; x = x & (x - 1); } while (x);
    return y;
}

Last

综上可以写出一段代码：

typedef unsigned long long ull;
typedef long long ll;
ull hbv(ull x) {
    ull y;
    do { y = x; x = x & (x - 1); } while (x);
    return y;
}

int main() {
    main_first;
    ull t, n, k; cin >> t;
    while (t--) {
        cin >> n >> k;
        ull k1 = hbv(k << 1), k2 = hbv((n << 1) - 1);
        if (k2 <= k1) {
            cout << (ull)log2(k2) << '\n';
        } else {
            cout << (n - k1 + k - 1) / k + (ull)log2(k1) << '\n';
        }
    }
    main_end;
}

可以根据自己需要自行实现

完整参考代码： VjudgeShared

#include <bits/stdc++.h>
using namespace std;
typedef __uint128_t ulll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long long ll;
template<typename T>
T getuint() {
    T x = 0; char c = getchar(); while (c > '9' || c < '0') c = getchar();
    while (c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
    return x;
}
template<typename T>
T getint() {
    T x = 0; char c = getchar(); bool neg = false;
    while (c > '9' || c < '0') { if (c == '-')neg = true; c = getchar(); }
    while (c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
    return x;
}
#define Unlock
#ifdef DEBUG
#define main_end cout << endl;system("pause");return 0
#else
#define main_end cout << flush;return 0
#endif
#ifdef Unlock
#define main_first ios::sync_with_stdio(false);cin.tie(nullptr)
#else
#define main_first cin.tie(nullptr)
#endif
#define range(i,n) for(ull i=0;i<n;++i)
#define bitelim(it,n) for(ull x=n,it=x&-x;x;x^=it,it=x&-x)
#define foreach(it,iterable) for(auto it=iterable.begin();it!=iterable.end();++it)
#define gcd __gcd
#define count_bits __builtin_popcountll
#define loop for(;;)
#define vecprint(vec) for(auto&&v:vec) cout<<v<<' ';cout

ull hbv(ull x) {
    ull y;
    do { y = x; x = x & (x - 1); } while (x);
    return y;
}

int main() {
    main_first;
    ull t, n, k; cin >> t;
    while (t--) {
        cin >> n >> k;
        ull k1 = hbv(k << 1), k2 = hbv((n << 1) - 1);
        if (k2 <= k1) {
            cout << (ull)log2(k2) << '\n';
        } else {
            cout << (n - k1 + k - 1) / k + (ull)log2(k1) << '\n';
        }
    }
    main_end;
}