「RiOI-2」hacker

Luogu

IDLGP9496

Time1000ms

Memory128MB

DifficultyP1

洛谷原创O2优化位运算洛谷月赛

现在有正整数 $n$，有以下操作； - 「ACCEPT」。花费 $1$ 的代价，将 $n$ [二进制](https://oi-wiki.org/math/base/#%E4%BA%8C%E8%BF%9B%E5%88%B6)**按位或**上一个正整数。 - 「BOTH」。花费 $1$ 的代价，将 $n$ [二进制](https://oi-wiki.org/math/base/#%E4%BA%8C%E8%BF%9B%E5%88%B6)**按位与**上一个正整数。两种操作均可使用多次（或不用），请求出将 $n$ 变为 $m$ 最小的代价。 [帮助：什么是按位与和按位或](https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96) ## Input **本题有多组数据。** 第一行一个正整数 $T$ 表示数据组数。接下来 $T$ 行，每行两个正整数 $n, m$ 以空格隔开。 ## Output 输出 $T$ 行，每行一个整数，表示答案。 [samples] ## Background 在小树丛边坐落着一个幻想的城堡。这里是 E 国的领地，而小 E，则是 E 国之王。现在，伟大的 E 国之王正在披挂出征。不过听说 E 国之王遇见了两个叫 ACCEPT 和 BOTH 的人，他们是谁？ ## Note ### 样例解释 + 对于 $n = 1$，$m = 1$，不需要任何操作。 + 对于 $n = 4$，$m = 5$，一种可行的方案为使用「ACCEPT $1$」。 + 对于 $n = 1$，$m = 4$，一种可行的方案为依次使用「ACCEPT $998{,}244{,}853$」和「BOTH $14$」。 ### 数据规模与约定 **本题开启捆绑测试。** | $\text{Subtask}$ | 分值 | $T \leq$ | $n, m \leq$ | | :--------------: | :--: | :------: | :---------: | | $0$ | $30$ | $100$ | $100$ | | $1$ | $70$ | $2\times 10^5$ | $10^{18}$ | 对于所有数据，$1\le T\le2\times 10^5$，$1\le n,m\le10^{18}$。

Samples

Input #1

Output #1

0
1
2

API Response (JSON)

{
  "problem": {
    "name": "「RiOI-2」hacker",
    "description": {
      "content": "现在有正整数 $n$，有以下操作； - 「ACCEPT」。花费 $1$ 的代价，将 $n$ [二进制](https://oi-wiki.org/math/base/#%E4%BA%8C%E8%BF%9B%E5%88%B6)**按位或**上 一个正整数。 - 「BOTH」。花费 $1$ 的代价，将 $n$ [二进制](https://oi-wiki.org/math/base/#%E4%BA%8C",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9496"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "现在有正整数 $n$，有以下操作；\n\n- 「ACCEPT」。花费 $1$ 的代价，将 $n$ [二进制](https://oi-wiki.org/math/base/#%E4%BA%8C%E8%BF%9B%E5%88%B6)**按位或**上 一个正整数。\n- 「BOTH」。花费 $1$ 的代价，将 $n$ [二进制](https://oi-wiki.org/math/base/#%E4%BA%8C...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments