🐰🐱 兔猫信奥学院：加菲老师的“神秘版本”考验

题目描述

加菲老师让小兔和小猫参与软件研发大赛，每当学院发布一个新版本的魔法管理系统，就会进行严格的质量检测。由于新版本是基于之前版本不断迭代的，一旦某个版本出现缺陷，那么该版本之后的所有版本都会继承这个错误。

现在，学院一共有编号 1 到 n 的版本，恰好某个版本第一次出现了缺陷（称为 “坏版本”），之后的版本全部不通过测试。请你帮助小兔和小猫找出第一个坏版本的编号，以便及时回滚和修复。

你可以调用预先定义的接口

// 模拟的 API：返回当前版本是否是坏版本
bool isBadVersion(int version) {
    static int bad = -1;  // 静态变量：首次初始化后不再改变

    if (bad == -1) {
        // 第一次调用时随机生成一个坏版本
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<int> dist(1, INT_MAX); // 支持大范围 n，例如 2^31 - 1
        bad = dist(rng);  // 随机生成一个坏版本号
    }

    return version >= bad;
}

来判断指定版本是否有缺陷。请尽量减少调用该接口的次数，实现时间复杂度为 O(log n) 的算法。

---

输入格式

n bad

• 第一行包含两个整数
  • n：版本总数（版本编号从 1 到 n）
  • bad：第一个坏版本的编号

（在实际比赛中，bad 不会直接给出，但为了离线评测，我们在输入中提供它，isBadVersion 接口内部会使用它来判定。）

---

输出格式

ans

• 输出一个整数 ans，表示第一个坏版本的编号。

---

数据范围

• 1 ≤ bad ≤ n ≤ 2³¹ − 1

---

输入输出样例

样例 1

5 4

输出：

4

解释：
版本 3 检测良好，版本 5 检测失败，版本 4 是首个失败版本。

---

样例 2

1 1

输出：

1

解释：
唯一版本就是坏版本。