#g6004. [GESP6级模拟题]图书管理

[GESP6级模拟题]图书管理

题目背景

学校图书馆的图书采用了一套"二叉树分类系统"对图书进行管理。

所有图书的分类编号规则如下:

  • 根类别编号为 11
  • 若某个类别的编号为 ii,则它的左子类别编号为 2i2i,右子类别编号为 2i+12i+1

这样,每一本书的分类编号就对应了二叉树中的一个节点。

例如,编号为 55 的图书,其分类路径为:1251 \to 2 \to 5,即根类别下的右子类(22)再向右子类(55)。

现在,管理老师想快速了解任意两个图书类别之间"隔了多少层"。

题目描述

给定两个图书的分类编号 uuvv,求它们之间的距离

距离定义为:在分类二叉树中,从一个节点走到另一个节点所需经过的最少边数。

输入格式

一行,两个正整数 u,vu, v,表示两个图书的分类编号。

输出格式

输出一个整数,表示 uuvv 之间的距离。

样例输入

5 6

样例输出

4

样例解释

分类二叉树的结构如下(只画出部分):

      1
     / \
    2   3
   / \ / \
  4  5 6  7
  • 5566 的最短路径为:521365 \to 2 \to 1 \to 3 \to 6,共 44 条边。

数据范围

1u,v1091 \le u, v \le 10^9