自动搬运

查看原文

来自洛谷，原作者为

	YCSluogu AFO | 互关一定要私信啊！人Q：3113929638 | 备赛ing...... | prufer 序列真的…… | sakana~~~

搬运于2025-08-24 22:35:55，当前版本为作者最后更新于2022-02-08 11:55:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里提供一个新奇的思路。

大家考虑一个弱化情况：如果只允许除以 $2$ 和加一并且 $a > b$。会怎么做？

这就非常容易考虑。让 $a$ 不断加 $1$ 与除以 $2$ 直到 $b > a$，这样 $a$ 便可以一路加到 $b$ 去。

大家推样例是否发现这样一个情况：$a$ 会一开始不断除以 $2$ 和加 $1$，一旦开始乘 $2$ 后就不会再除以 $2$。 原因其实很好理解，若除以 $2$ 后乘 $2$ 对答案不会更优。

啧……是不是就和我们弱化情况开始有点类似了呢？也就是说，我们需要找一个数 $t$，作为我们的中转值。 负责让我们完成弱化情况。那么这个中转值，要满足什么条件？

后面只允许乘 $2$ 和加 $1$。所以，$t$ 的二进制一定是 $b$ 二进制表示下的一个前缀。

所以，我们只需要枚举 $b$ 二进制前缀表示的数字，即 $t$。然后按照弱化情况求出 $a$ 变为 $t$ 所花的次数。 这都求出来了，还想不到后面怎么写？不断将 $a$ 乘 $2$ 和加 $1$，使其与 $b$ 的前缀保证相同即可。

code

#include <bits/stdc++.h>

using namespace std;

long long n;

long long len(long long num) {
  for (long long i = 63; i >= 0; i--) {
    if ((num >> i) & 1) {
      return i + 1;
    }
  }
  return 0;
}

long long get(long long num, long long i, long long len) {
  return num >> (len - i);
}

void solve() {
  long long a, b, c, cnt = 0, ans = INT_MAX;
  cin >> a >> b;
  if (a == b) {
    cout << 0 << endl;
    return;
  }
  c = len(b);
  long long save = a;
  for (long long i = 1; i <= c; i++, ans = min(ans, cnt), a = save) {
    cnt = 0;
    long long nowb = get(b, i, c);
    while (a != nowb) {
      if (a > nowb) {
        if (a & 1) a++;
        else a /= 2;
        cnt++;
      } else {
        cnt += nowb - a;
        a = nowb;
      }
    }
    for (long long j = i + 1; j <= c; j++) {
      nowb = get(b, j, c);
      a <<= 1;
      cnt++;
      if (nowb != a) a++, cnt++;
    }
  }
  cout << ans << endl;
}

int main() {
  cin >> n;
  while (n--) {
    solve();
  }
  return 0;
}