T14:Equalization

关键观察

把一个数除以 2^k 并向下取整，等价于对它做一次右移 k 位：

• floor(x / 2^k) = x >> k

因为操作可以做很多次，所以对同一个数连续做几次就是累计右移：

• 选了 k1, k2, ... 作用在 x 上，最终变成 x >> (k1+k2+...)

代价是这些 2^k 的和。

额外限制：每个 k 全局最多用一次，也就是说同一个 k 不能同时用于 x 和 y，也不能重复用于同一个数。

---

目标转成“选 k 分配给 x / y / 不用”

你最终会让：

• x' = x >> sx
• y' = y >> sy

其中 sx 是分配给 x 的所有 k 的和，sy 是分配给 y 的所有 k 的和，并且用到的 k 互不重复。

要求 x' == y'，并让总代价最小。

---

预处理 DP：先算出每个 (sx, sy) 的最小代价

因为 x, y <= 1e17，最多也就 60 位左右，右移超过 60 基本都变 0，所以只需要考虑：

• sx, sy 都在 0..60 之间

做一个“背包式”的 DP，枚举 k=1..60，每个 k 有三种选择：

1. 不用 k
2. 把 k 分配给 x（sx += k，代价 += 2^k）
3. 把 k 分配给 y（sy += k，代价 += 2^k）

这样就能得到 best[sx][sy]：实现这对总右移量的最小代价（自动保证 k 不重复，因为每个 k 只处理一次）。

---

每个测试用例怎么用

对每个测试用例 (x,y)：

• 枚举 sx=0..60，sy=0..60
• 如果 (x >> sx) == (y >> sy)，就用 best[sx][sy] 更新答案最小值

复杂度：

• 预处理一次：大约 60 * 61 * 61，很小
• 每组数据：枚举 61*61=3721 次，t=1e5 也能接受

---

C++ 代码

#include <bits/stdc++.h>
using namespace std;

static const long long INF = (1LL<<62);
static long long bestCost[61][61];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预处理 bestCost[sx][sy]
    for (int i = 0; i <= 60; i++)
        for (int j = 0; j <= 60; j++)
            bestCost[i][j] = INF;
    bestCost[0][0] = 0;

    for (int k = 1; k <= 60; k++) {
        long long c = 1LL << k; // 2^k
        // 用一个新数组做转移，避免同一轮重复使用 k
        static long long nxt[61][61];
        for (int i = 0; i <= 60; i++)
            for (int j = 0; j <= 60; j++)
                nxt[i][j] = bestCost[i][j]; // 选择：不用 k

        for (int sx = 0; sx <= 60; sx++) {
            for (int sy = 0; sy <= 60; sy++) {
                long long cur = bestCost[sx][sy];
                if (cur >= INF) continue;

                // 分给 x
                if (sx + k <= 60) {
                    nxt[sx + k][sy] = min(nxt[sx + k][sy], cur + c);
                }
                // 分给 y
                if (sy + k <= 60) {
                    nxt[sx][sy + k] = min(nxt[sx][sy + k], cur + c);
                }
            }
        }

        for (int i = 0; i <= 60; i++)
            for (int j = 0; j <= 60; j++)
                bestCost[i][j] = nxt[i][j];
    }

    int t;
    cin >> t;
    while (t--) {
        unsigned long long x, y;
        cin >> x >> y;

        long long ans = INF;

        for (int sx = 0; sx <= 60; sx++) {
            unsigned long long xx = (sx >= 64 ? 0ULL : (x >> sx));
            for (int sy = 0; sy <= 60; sy++) {
                unsigned long long yy = (sy >= 64 ? 0ULL : (y >> sy));
                if (xx == yy) {
                    ans = min(ans, bestCost[sx][sy]);
                }
            }
        }

        cout << ans << "\n";
    }
    return 0;
}