考拉茲距離 題解｜APCS 2026 年 11 月中高級 第 3 題

前置知識

怎麼找出全部可行的數，下面會從頭推導；要先讀的是找「最近的那一個」用到的工具：

• 二分搜與 lower_bound：NTUCPC Guide〈搜尋〉的「第一個 \(\geq k\) 的數」與「二分搜 in STL」——在由小到大排好的陣列裡，找第一個 \(\ge k\) 的位置只要 \(O(\log n)\)；lower_bound(起點, 終點, k) 直接回傳那個位置，減掉 begin() 就是索引。吳邦一《AP325》第 2 章 2.2 節「搜尋」講同樣兩件事：自己寫的二分搜和 lower_bound（教材 PDF 第 39～44 頁；Python 版第 2 章用的是 bisect_left）。
• 整數溢位：語法書 2.9——int 大約只到 \(2.1 \times 10^9\)、long long 大約到 \(9.2 \times 10^{18}\)，算出來的數超過就會溢位。

簡潔題意

一次考拉茲操作把奇數 \(n\) 變成 \((3n+1)/2\)、偶數 \(n\) 變成 \(n/2\)。給目標 \(t\) 和次數上限 \(m\)：做至多 \(m\) 次操作（可以是 \(0\) 次，所以 \(t\) 本身也算）就會變成 \(t\) 的正整數，叫做可行的數。接著有 \(q\) 筆詢問，每筆給一個 \(a_i\)，輸出 \(a_i\) 和最近的可行數的距離（\(1 \le t \le 10^9\)，\(0 \le m \le 31\)，\(1 \le q \le 9999\)，\(1 \le a_i \le 10^{18}\)）。（APCS 逐筆給分。）

往前算不知道從哪裡試起：從 \(t\) 往回推

往前算很簡單：拿一個數照規則做 \(m\) 次，看中途有沒有變成 \(t\)。問題是要拿哪些數來試——可行的數最大會到 \(2 \times 10^{18}\) 左右（下一節會算），一個一個試不完。從 \(a\) 開始往兩邊一個一個試也不行：答案可能接近 \(10^{18}\)，例如 \(t = 7\)、\(m = 0\)、\(a = 10^{18}\)，答案是 \(10^{18} - 7\)。

反過來問：做一次操作會變成 \(y\) 的數有哪些？

• 偶數 \(x\)：\(x / 2 = y\)，所以 \(x = 2y\)。\(2y\) 一定是偶數，這一個永遠都有。
• 奇數 \(x\)：\((3x + 1) / 2 = y\)，所以 \(x = (2y - 1) / 3\)。它要是整數，\(2y - 1\) 就要能被 \(3\) 整除：\(y\) 除以 \(3\) 餘 \(0\)、\(1\)、\(2\) 時，\(2y - 1\) 除以 \(3\) 分別餘 \(2\)、\(1\)、\(0\)，所以只有 \(y\) 除以 \(3\) 餘 \(2\) 時才有這一個。它也一定是奇數：\(3x = 2y - 1\) 是奇數，而偶數乘以 \(3\) 還是偶數，所以 \(x\) 不會是偶數——奇數的規則正好用得上。

所以每個數的「前一步」最多兩個：\(2y\)，以及 \(y\) 除以 \(3\) 餘 \(2\) 時的 \((2y - 1)/3\)。

把「剛好做 \(k\) 次操作會變成 \(t\) 的數」叫做第 \(k\) 層：第 \(0\) 層只有 \(t\)；第 \(k\) 層就是第 \(k - 1\) 層每個數的前一步。推到第 \(m\) 層，第 \(0\)～\(m\) 層合起來就是全部可行的數。圖 1 是範例 2（\(t = 5\)、\(m = 4\)）：\(5\) 除以 \(3\) 餘 \(2\)，前一步是 \(10\) 和 \(3\)；\(10\) 餘 \(1\)，只有 \(20\)；\(3\) 是 \(3\) 的倍數，乘以 \(2\) 還是 \(3\) 的倍數，之後一路只有 \(6\)、\(12\)、\(24\)。一層一層和題目的表格對得起來。

可行的數最大到 \(2 \times 10^{18}\)，超過 \(10^{18}\) 的也不能丟

• 多大：往回推一步，\(2y\) 是兩倍，\((2y - 1)/3\) 比 \(y\) 還小，所以第 \(k\) 層的數都不超過 \(t \cdot 2^k\)。最大的可行數是 \(t \cdot 2^m \le 10^9 \times 2^{31} \approx 2.15 \times 10^{18}\)，比 \(a_i\) 的上限 \(10^{18}\) 還大，要用 long long（上限約 \(9.2 \times 10^{18}\)，放得下）。
• 超過 \(10^{18}\) 的不能丟：\(a_i\) 不超過 \(10^{18}\)，最近的可行數卻可能比 \(10^{18}\) 大。例如 \(t = 10^9\)、\(m = 30\)、\(a = 10^{18}\)：不超過 \(10^{18}\) 的可行數裡最大的是 \(536870912000000000\)，差 \(463129088000000000\)；比 \(10^{18}\) 大的可行數裡最小的是 \(t \cdot 2^{30} = 1073741824000000000\)，只差 \(73741824000000000\)。
• 有幾個：每個數都有前一步 \(2y\)，大約三分之一的數還有第二個，所以每一層大約是上一層的 \(4/3\) 倍。\(m = 31\) 時全部加起來通常是幾萬個；我們用程式找到最多的是 \(t = 871696100\)，共 \(78092\) 個。

\(t = 1\) 時 \(1 \to 2 \to 1\) 會繞圈，同一個數會出現在好幾層（\(1\) 在第 \(0\)、\(2\)、\(4\)……層都有）。下一步要排序，重複的數會排在一起，不影響找最近的，不用特別處理。

找最近的：排好序，只要看兩個數

有了全部可行的數，最直接的做法是每筆詢問把它們全部看一遍、取距離最小的。答案一定對，但最壞要比較約 \(9999 \times 78092 \approx 7.8 \times 10^8\) 次。

先把可行的數由小到大排好。離 \(a\) 最近的可行數只可能是這兩個之一：

• 第一個 \(\ge a\) 的：lower_bound 找到它的位置 \(j\)；
• 它的前一個：第 \(j - 1\) 個，也就是比 \(a\) 小的可行數裡最大的。

其他可行的數不是排在第 \(j\) 個後面、就是排在第 \(j - 1\) 個前面，離 \(a\) 都不會更近。兩個各算距離、取小的。\(j = 0\) 時 \(a\) 比所有可行數都小，沒有前一個；\(j\) 等於可行數的個數時 \(a\) 比全部都大，沒有第 \(j\) 個；\(a\) 本身可行時，第 \(j\) 個就是 \(a\)，距離 \(0\)。圖 2 是範例 2 的五筆詢問：

每筆詢問的二分搜只要比較約 \(17\) 次（\(2^{17} > 78092\)），\(9999\) 筆加起來約 \(1.7 \times 10^5\) 次。

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

int main() {
    long long t;
    int m, q;
    cin >> t >> m >> q;

    vector<long long> cand = {t};    // 全部可行的數，先放第 0 層的 t
    vector<long long> layer = {t};   // 上一層：剛好做 k - 1 次操作會變成 t 的數
    for (int k = 1; k <= m; k++) {
        vector<long long> before;    // 這一層：做一次操作會變成上一層某個數的數
        for (long long y : layer) {
            before.push_back(2 * y);                           // 偶數 2y：除以 2 就是 y
            if (y % 3 == 2) before.push_back((2 * y - 1) / 3); // 奇數 (2y-1)/3：(3x+1)/2 就是 y
        }
        for (long long x : before) cand.push_back(x);
        layer = before;
    }
    sort(cand.begin(), cand.end());
    int K = cand.size();

    for (int i = 0; i < q; i++) {
        long long a;
        cin >> a;
        int j = lower_bound(cand.begin(), cand.end(), a) - cand.begin();   // 第一個 >= a 的位置
        long long best = LLONG_MAX;
        if (j < K) best = cand[j] - a;                     // 第 j 個：>= a 的最小可行數
        if (j > 0) best = min(best, a - cand[j - 1]);      // 第 j - 1 個：< a 的最大可行數
        cout << best << '\n';
    }
    return 0;
}

設可行的數有 \(K\) 個：往回推 \(O(K)\)、排序 \(O(K \log K)\)、每筆詢問 \(O(\log K)\)。可行的數最多、詢問也最多的情況（下面自測表第 4 列），本站實測約 \(0.06\) 秒。每筆詢問全部看一遍的寫法，同一筆 C++ 本站實測約 \(0.55\) 秒，還在時限內；Python 同樣的寫法超過時限。

測過再交：範例的數都很小

兩個範例的可行數都在 \(100\) 以內、\(m\) 都不是 \(0\)，答案也都很小。沒蓋到的：\(m = 0\)、答案超過 int、最近的可行數比 \(10^{18}\) 大、往回推的路上經過比 \(10^{18}\) 大的數、可行的數最多。

四筆都親眼看過正確，這題就穩了。