Codeforces 251C Number Transformation：數論與 BFS 混合求解最小步數

題目大意

給定 a, b (1 ≤ b ≤ a ≤ 10^18)、k (2 ≤ k ≤ 15)。每秒可執行兩種操作之一：

1. a = a - 1
2. 選擇 x ∈ [2, k]，a = a - (a mod x)（即減到最近的 x 的倍數）

求將 a 變為 b 的最少秒數。

核心觀察

• 操作 2 會把 a 變成某個 x 的倍數。對所有 x∈[2,k]，a 會變成 LCM(2..k) 的倍數。
• 設 M = LCM(2..k)。若 a = q·M + r，最快減到 q·M 再 -1 進入 (q-1)·M + (M-1)，再重複。
• 因此可將大數跳躍：先處理 a % M，再按 M 為單位批量跳躍，最後剩餘 < M 部分用 BFS 解決。

演算法流程

1. 計算 M = LCM(2..k)（最大 k=15 時 M=360360）。
2. DP 預處理 dp[i] = 從 i 減到 0 的最小步數（i < M），遞歸 + 記憶化。
3. 若 a - a%M > b：先處理尾巴 a % M，再批量跳躍 (a - b) / M 個完整週期，每週期花費 1 + dp[M-1] 步（-1 + 從 M-1 減到 0）。
4. 剩餘 a - b < M 部分，在模 M 空間內 BFS 求最短路。

關鍵代碼片段

int dp[MAXM], vis[MAXM], sp[MAXM];
long long q[MAXM];

int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }

int dfs(int x) { // 記憶化遞歸求 dp
    if (dp[x] != -1) return dp[x];
    int res = INF;
    for (int i = 2; i <= k; i++)
        if (x % i) res = min(res, dfs(x - x%i));
    res = min(res, dfs(x-1));
    return dp[x] = res + 1;
}

int bfs(int st, int ed) { // 模 M 空間 BFS
    memset(vis, 0, sizeof(vis));
    int head = 0, tail = 0;
    q[tail] = st; sp[tail++] = 0; vis[st] = 1;
    while (head < tail) {
        if (q[head] == ed) return sp[head];
        for (int i = 2; i <= k; i++) {
            int nxt = q[head] - q[head] % i;
            if (!vis[nxt]) { vis[nxt]=1; q[tail]=nxt; sp[tail]=sp[head]+1; tail++; }
        }
        if (!vis[q[head]-1]) { vis[q[head]-1]=1; q[tail]=q[head]-1; sp[tail]=sp[head]+1; tail++; }
        head++;
    }
    return -1;
}

int main() {
    long long a, b; int k;
    while (~scanf("%lld%lld%d", &a, &b, &k)) {
        int M = 1;
        for (int i = 2; i <= k; i++) M = M / gcd(M, i) * i;
        memset(dp, -1, sizeof(dp)); dp[0] = 0;
        for (int i = 1; i < M; i++) dfs(i);

        long long ans = 0;
        if (a - a%M > b) {
            ans += dp[a%M]; a -= a%M;
        }
        long long diff = a - b;
        long long cycles = diff / M;
        a -= cycles * M;
        ans += cycles * (1 + dp[M-1]);

        diff = a - b;
        if (diff > 0) {
            if (a % M == 0) ans += bfs((a-1)%M, b%M) + 1;
            else ans += bfs(a%M, b%M);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度分析

• M ≤ 360360，DP 與 BFS 皆在 O(M·k) 內，極快。
• 大數跳躍 O(1)。
• 總體毫秒級通過。

解題心得

1. 發現 LCM 週期性是關鍵，將 10^18 規模壓縮到 M 內。
2. 「批量跳躍 + 餘數 BFS」是處理大數最短路的經典套路。
3. 注意 a%M==0 時必須先 -1 再 BFS，否則操作 2 無效。