玩家需要从 $1$ 号点移动到 $E$ 号点；我们可以反向思考，求从目标位置 $E$ 回退到起点 $1$ 的最少步数。由于题目保证 $1 \le k \le p$ 且要求最少的使用次数，在可能的情况下，优先使用“反向倍数骰子”（即整除 $p$）能够最快地缩小距离。

• 特殊情况 $p=1$：此时倍数骰子（直达 $x * p$ 号点）失去了加速作用，玩家只能全程使用指定骰子。从起点 $1$ 到 $E$ 的总距离为 $E - 1$，而指定骰子每次最多移动 $k$ 步，因此最少次数为 $\lceil (E - 1) / k \rceil$。
• 一般情况 $p > 1$：当当前位置 $E > 1$ 时，通过循环处理以下三种状态：
  • $E < p$：此时无法再使用倍数骰子（因为起点必须是正整数），只能依靠指定骰子从 $1$ 一步步移动过来。所需的最少步数为 $\lceil (E - 1) / k \rceil$，累加后即可结束计算。
  • $E \pmod p \neq 0$：说明在正向移动时，到达当前 $E$ 号点的最后一段是通过指定骰子走完的。我们将其退回到最近的 $p$ 的倍数，需要回退的距离为 $E \pmod p$。所需次数为 $\lceil (E \pmod p) / k \rceil$，然后将 $E$ 更新为这个最近的倍数。
  • $E \pmod p == 0$：此时可以直接使用逆向的倍数骰子，将 $E$ 除以 $p$，计作使用了 $1$ 次骰子。

由于每次循环都能将 $E$ 减小到 $p$ 的倍数并除以 $p$（$p \ge 2$），循环执行的最大次数约为 $\log_2(10^{18}) \approx 60$ 次。

Sam的大富翁 题解

题目分析

从 1 出发，每次有两种操作：

1. 使用加法骰子，可以让当前数字增加 1~k；
2. 使用乘法骰子，可以让当前数字变成原来的 p 倍。

要求到达 E 的最少操作次数。

---

1. DP

当 E 比较小时，可以直接设：

$$dp[i]=从1到达i的最少操作次数$$

从 i 出发，可以转移到：

$$i+1,i+2,\cdots,i+k$$

以及：

$$i\times p$$

所以直接枚举即可，复杂度为 O(Ek)。

代码中的 solve(E) 就是这个 DP：

void solve(int E){
    for(int i=1;i<=E;i++) dp[i]=INF;
    dp[1]=0;
    for(int i=1;i<=E;i++){
        for(int j=1;j<=k&&i+j<=E;j++)
            dp[i+j]=min(dp[i+j],dp[i]+1);
        if(i*p<=E)
            dp[i*p]=min(dp[i*p],dp[i]+1);
    }
}

---

2.

当 E 很大时，不能直接 DP。

考虑最后一次使用乘法。假设乘法前到达：

$$q=\lfloor E/p\rfloor$$

那么做一次乘法后：

$$q\rightarrow q\times p$$

由于：

$$E=qp+r$$

其中：

$$r=E\bmod p$$

所以乘法之后还差 r，只需要再进行：

$$\left\lceil\frac r k\right\rceil$$

次加法。

因此，如果采用这种方案，答案就是：

$$f(q)+1+\left\lceil\frac{r}{k}\right\rceil$$

其中 +1 表示最后进行的那一次乘法。

于是可以递归：

int solveb(int E){
    if(E<=100005){
        solve(E);
        return dp[E];
    }
    int q=E/p;
    int r=E%p;
    int need=solveb(q)+1;
    if(r) need+=(r+k-1)/k;
    return need;
}

这里的好处是每次递归都会变成 E/p，所以 E 会快速变小，最多只有 O(log_p E) 层。

---

3. 为什么 q=E/p

这里利用了题目的条件：

$$k<p$$

假设最后一次乘法前到达的是比 E/p 更小的数，例如 q-1。

把它提高到 q，最多只需要一次加法；但是乘法以后：

$$(q-1)p\rightarrow qp$$

增加了 p，而一次加法最多只能增加 k，由于 p>k，因此这样不会让答案变差。

所以最后一次乘法之前可以直接取最大的：

$$q=\lfloor E/p\rfloor$$

---

4. 还要考虑完全不乘

上面的递归方案默认使用了乘法，但有的同学就会说了：欸！直接加法会不会比乘法更优？实际上是不会的,因为$k \le p$， 所以在能出现走p的情况下，肯定是走p的，否则刚刚的式子也能成立

特别地，当 p=1 时，乘法相当于不动，所以直接只考虑加法。

完整代码

#include<bits/stdc++.h>
using namespace std;
const int B = 5000;
const int INF=1e9;
long long  k, p;
#define int long long
int dp[100005];
void solve(int E) {
    
    for(int i=1;i<=E;i++) {
        dp[i]=INF;
    }
    dp[1]=0;
    for(int i = 1; i <= E; i++){
        for(int j = 1; j <= k && i + j <= E; j++) {
            dp[i + j] = min(dp[i + j], dp[i] + 1);
        }
        if(i * p <= E) {
            dp[i * p] = min(dp[i * p], dp[i] +1);
        }   
    }
}
// }
// int solveb(int E){
//     if(E <= 100005){
//         solve(E);
//         return  dp[E];
//     }
//     int need = solveb(E/p);
//     int k1 = E/p;
//     need += (k1 + k - 1) / k + 1;
//     return need;
// }
int solveb(int E){
    if(E<=100004){
        solve(E);
        return dp[E];
    }

    int q=E/p;
    int r=E%p;

    int need=solveb(q);

    need+=1;

    if(r)
        need+=(r+k-1)/k;

    return need;
}
signed main(){
     freopen("dice.in", "r", stdin);
     freopen("dice.out", "w", stdout);
     
    long long E;
    cin >> k >> p >> E;
       if (p == 1) {
        if (E == 1) {
            cout << 0;
            return 0;
        }
        cout << (E - 2) / k + 1;
        return 0;
    }
        cout <<  solveb(E);
    
    return 0;
}

复杂度： E<100005 时为 O(Ek)；E 很大时，每次递归除以 p，复杂度约为 O(log_p E)。

对 $E$ 不断的进行 $/p$ 的操作，期间的余数使用 $+1\sim k$ 消掉。当 $E$ 比某一个阈值（例如 $5000$ ）时直接 DP 。复杂度 $O(\log E)$ 。