Codeforces 251C Number Transformation：大數範圍下的動態規劃與 BFS 混合解法

題目大意

給定 a, b (1≤b≤a≤10¹⁸), k (2≤k≤15)。兩種操作：1) a = a-1；2) 選 x∈[2,k]，a = a - (a mod x)。求最少步數將 a 變為 b。

核心觀察與數學建模

1. 操作 2 使 a 變為 x 的倍數（向下取整到最近的 x 的倍數）
2. 設 M = lcm(2,3,...,k) (k≤15 時 M=360360)，M 很小
3. 將 a 寫為 a = q·M + r (0≤r
4. 關鍵：對於固定 r，從 q·M+r 到 q·M 的最優步數固定，記為 dp[r]
5. 從 q·M 到 (q-1)·M 必須先 -1 變為 q·M-1，再用操作 2，步數 = 1 + dp[M-1]

算法流程

1. 預計算 dp[0..M-1]：dp[i] = 從 i 到 0 的最少步數（BFS 或 DP）
2. 若 a - a%M > b：先處理尾部 r = a%M，步數 += dp[r]，a -= r
3. 整段跳躍：每減少 M 需 1+dp[M-1] 步，計算可跳躍段數
4. 剩餘部分 a-b < M：BFS 精確求解

完整 C++ 代碼

#include 
using namespace std;

const int MAXM = 360360;  // lcm(1..15)
int dp[MAXM], k;
int vis[MAXM], sp[MAXM];
long long q[MAXM];
int head, tail;

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

int dfs(int x) {
    if (dp[x] != -1) return dp[x];
    int ret = 0x3f3f3f3f;
    for (int i = 2; i <= k; i++)
        if (x % i) ret = min(ret, dfs(x - x%i));
    ret = min(ret, dfs(x-1));
    return dp[x] = ret + 1;
}

int bfs(int st, int ed) {
    memset(vis, 0, sizeof(vis));
    head = tail = 0;
    q[tail] = st; sp[tail++] = 0; vis[st] = 1;
    while (head < tail) {
        long long u = q[head]; int d = sp[head++];
        if (u == ed) return d;
        for (int i = 2; i <= k; i++) {
            long long v = u - u%i;
            if (!vis[v]) { vis[v]=1; q[tail]=v; sp[tail++]=d+1; }
        }
        long long v = u-1;
        if (!vis[v]) { vis[v]=1; q[tail]=v; sp[tail++]=d+1; }
    }
    return -1;
}

int main() {
    long long a, b;
    while (~scanf("%lld%lld%d", &a, &b, &k)) {
        int M = 1;
        for (int i = 2; i <= k; i++) M = M*i/gcd(M,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 jump = diff / M;
        a -= jump * M;
        ans += jump * (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;
}

關鍵技術點解析

狀態空間縮減原理圖解

a = q·M + r
     ↓ 處理尾部 r (dp[r] 步)
a = q·M
     ↓ -1 變為 q·M-1 (1步)
     ↓ 操作2 系列到 (q-1)·M (dp[M-1] 步)
a = (q-1)·M
     ... 重複 jump 次 ...
剩餘 < M 部分 → BFS 精確求解

樣例驗證

Input: 10 1 4
M = lcm(2,3,4) = 12
dp[10] = 6 路徑: 10→8→6→4→3→2→1
Output: 6 ✓

Input: 1000000000000000000 1 3
M = lcm(2,3) = 6
dp[5] = 3, dp[5] = 3, 1+dp[5]=4
jump = (10¹⁸-1)/6 ≈ 1.666e17
ans = 666666666666666667 ✓

總結

此題展示了如何處理超大數值範圍的最短路問題：利用數學周期性將狀態空間壓縮，預計算小空間最優解，大空間按周期跳躍。LCM 分塊 + DP/BFS 混合是解決此類問題的通用模板。