满分解法（100 分）

先分开递增与取模

记实际还需执行的操作数为 $t=N-1$。当当前值 $a>0$ 时，

$$1\le \operatorname{big}(a)\le9.$$

因此，在下一次越过 $M$ 之前，数值严格增加。困难在于一段这样的递增过程可能非常长，不能逐天计算。

越过 $M$ 的那一步之前，数值至多为 $M-1$，之后至多为 $M+8$。取模后的值只可能是

$$0,1,\ldots,8.$$

其中 $0$ 会永远保持不变。其他入口值的后续过程也唯一确定，重复出现同一个入口值时可以跳过循环。这样，问题分成两部分：快速走完递增段，再在少量入口值上找循环。

固定高位时，只关心它的最大数位

考虑十进制块

$$[P\cdot10^k,\ (P+1)\cdot10^k-1].$$

在没有走出这个块时，数可写为 $P\cdot10^k+y$，其中 $y$ 是补齐前导零后的 $k$ 位后缀。设 $d=\operatorname{big}(P)$，则每一步给后缀增加

$$\max(d,\operatorname{big}(y)).$$

高位前缀的具体数值不再影响块内轨迹，其最大数位 $d$ 已经足够。

还需要记录进入块的位置。由于一次最多加 $9$，从左侧第一次进入块时，只可能落在块首之后 $0$ 至 $8$ 的位置。走出块时，越过右边界的距离也至多为 $8$。

原始给定的 $A$ 可能在块中间，不满足这一入口条件。后面通过递归展开包含 $A$ 的块处理；这里只预处理能够反复复用的标准入口。

块跳转的状态与初始值

定义

$$F(k,d,s)=(f(k,d,s),g(k,d,s)),$$

其中 $0\le k\le18$、$0\le d\le9$、$0\le s\le8$。从某个长度为 $10^k$ 的块的偏移 $s$ 出发，在前缀最大数位为 $d$ 时：

• $f(k,d,s)$ 是第一次走到该块右侧所需的操作数；
• $g(k,d,s)$ 是走出后相对下一个块开头的偏移。

这两个量都要保存。只知道步数就无法衔接下一块，只知道出口就无法判断能否在剩余天数内走完。

例如，块 $[20,29]$ 的高位最大数位是 $2$，从偏移 $3$ 对应的 $23$ 出发：

$$23\longrightarrow26\longrightarrow32.$$

两步走出块，下一个块从 $30$ 开始，故 $F(1,2,3)=(2,2)$。

当 $k=0$ 时，块只有一个数：

• 若 $s=0$ 且 $d>0$，一步增加 $d$，相对下一个单点的偏移是 $d-1$；
• 若 $s\ge1$，上一步已经越过当前单点，不执行操作，只将偏移减去 $1$；
• 若 $s=d=0$，对应数值 $0$，无法离开。

即

$$F(0,d,s)= \begin{cases} (0,s-1),&s\ge1,\\ (1,d-1),&s=0,\ d>0,\\ (+\infty,0),&s=d=0. \end{cases}$$

允许“入口已经越过单点”是为了统一处理一步跨过多个数字的情形，并不是额外执行了操作。

对于任意 $k$，都有

$$F(k,0,0)=(+\infty,0).$$

其余状态出发时数值为正，每步严格增加，一定能走出块。

十个子块依次衔接

长度 $10^k$ 的块可以按下一位数字 $x=0,1,\ldots,9$ 分成十个长度 $10^{k-1}$ 的子块。进入第 $x$ 个子块后，它的高位最大数位变为 $\max(d,x)$。

令 $c_x$ 为已经经过前 $x$ 个子块的总步数，$s_x$ 为相对第 $x$ 个子块开头的偏移。初始化

$$c_0=0,\qquad s_0=s.$$

对 $x=0,1,\ldots,9$，顺序计算

$$(u_x,v_x)=F(k-1,\max(d,x),s_x),$$ $$c_{x+1}=c_x+u_x,\qquad s_{x+1}=v_x.$$

最后得到

$$F(k,d,s)=(c_{10},s_{10}).$$

这里必须按顺序传递偏移，不能把十个子块都当成从偏移 $0$ 开始。若某一步跳过了几个单点，前面的零步转移会把多余偏移逐个扣掉。

按 $k$ 从小到大填表即可。归纳地，子块转移精确表示原更新；上一个子块的出口正好是下一个子块的入口，所以顺序复合后仍是原过程，且保存了准确的总步数。

任意起点与剩余步数怎样处理

设正在访问的块为 $[l,r]$，长度 $10^k$，前缀最大数位为 $d$。当前值仍用 $a$ 表示，剩余步数为 $t$。

已经用完步数、已经到达模数，或者当前值已经越过块时，直接结束这次访问。对于尚未越过的块，若满足：

1. $r<M$，即整块都在取模前的合法范围内；
2. $0\le a-l\le8$，可以使用标准入口状态；
3. $f(k,d,a-l)\le t$，剩余步数足以走出这个块；

便执行整块跳转：

$$t\leftarrow t-f(k,d,a-l),\qquad a\leftarrow r+1+g(k,d,a-l).$$

否则，把块分成十个子块，按数值从小到大访问。子块的左端点和前缀最大数位分别是

$$l+x10^{k-1},\qquad \max(d,x).$$

当前值始终由已经执行的真实操作决定；被跨过去的子块直接略过，尚未跨过的子块继续处理。特别地：

• 起始值在大块内部时，先展开到包含它的位置；
• $M$ 截断了最后一个块时，只访问 $M$ 之前的部分；
• 剩余步数不足以走完整块时，向更小的块下降，精确停在目标位置。

下降到单点时，若仍有操作可做且 $a>0$，其一步转移必定可以执行，因此不会再下降到负的层数。外层遇到 $a=0$ 会直接结束。

根块取 $[0,10^{18}-1]$。一次根块访问会用完剩余步数，或者恰好执行到第一次越过 $M$；后一种情况再令 $a\leftarrow a\bmod M$。只在真正跨模数时产生回绕，不能在数字块边界处取模。

在取模后的入口值上跳过循环

每完成一段递增过程，就回到 $0,\ldots,8$ 中的一个值。若它为 $0$，答案已经确定。

对其余值，记录它第一次出现时的剩余步数。若相同值先后对应剩余步数 $t_0$ 和 $t$，那么

$$L=t_0-t>0$$

就是返回这个值所经历的操作数。由于后续由当前值唯一决定，再走 $L$ 步仍回到这里，因此可以令

$$t\leftarrow t\bmod L.$$

随后只需执行不足一圈的尾段。若余数为 $0$，当前值就是答案。

初始 $A$ 很大时，可以先走完第一段再记录小入口；初始 $A\le8$ 时，也可以立即记录它。记录的是操作数之差，不是跨过了多少次模数。

复杂度

时间复杂度为 $O(10^3D)$，其中 $D=18$。预处理有 $(D+1)\cdot10\cdot9$ 个状态，每个非初始状态合并十个子块。

一次根块访问只会展开起点附近和停止位置附近的路径；两者之间的完整块都能直接跳过。每层每条路径至多检查十个子块，所以每段花费 $O(10D)$。小入口状态至多九种，重复后只剩一个循环以内的尾段，因此这部分总共为 $O(10^2D)$。

空间复杂度为 $O(10^2D)$，用于完整跳转表；递归栈深度为 $O(D)$。

AC 代码（C++20）

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

void solve() {
  i64 a, mod, n;
  cin >> a >> mod >> n;
  n--;
  constexpr i64 inf = 1000000000000000001LL;
  vector<i64> pw(19, 1);
  for (int k = 1; k <= 18; k++) pw[k] = pw[k - 1] * 10;
  using state = pair<i64, int>;
  vector dp(19, vector(10, vector<state>(9)));
  for (int k = 0; k <= 18; k++) {
    for (int d = 0; d <= 9; d++) {
      for (int s = 0; s <= 8; s++) {
        if (d == 0 && s == 0) {
          dp[k][d][s] = {inf, 0};
        } else if (k == 0) {
          dp[k][d][s] = s > 0 ? state{0, s - 1} : state{1, d - 1};
        } else {
          i64 cnt = 0;
          int cur = s;
          for (int x = 0; x <= 9; x++) {
            auto [steps, nxt] = dp[k - 1][max(d, x)][cur];
            cnt += steps;
            cur = nxt;
          }
          dp[k][d][s] = {cnt, cur};
        }
      }
    }
  }

  auto calc = [&](auto&& self, int k, i64 l, int d) -> void {
    i64 r = l + pw[k] - 1;
    if (n == 0 || a >= mod || a > r || l >= mod) return;
    if (r < mod && a >= l && a - l <= 8) {
      auto [cnt, nxt] = dp[k][d][a - l];
      if (cnt <= n) {
        n -= cnt;
        a = r + 1 + nxt;
        return;
      }
    }
    for (int x = 0; x <= 9; x++) {
      self(self, k - 1, l + x * pw[k - 1], max(d, x));
    }
  };

  vector<i64> first(9, -1);
  while (n > 0 && a != 0) {
    if (a <= 8) {
      if (first[a] != -1) {
        n %= first[a] - n;
        if (n == 0) break;
      }
      first[a] = n;
    }
    calc(calc, 18, 0, 0);
    a %= mod;
  }
  cout << a << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

对完整数值使用 Floyd 找环（通过子任务 3–4，共 35 分）

数值相同，后续就相同

定义

$$h(x)=(x+\operatorname{big}(x))\bmod M.$$

当前数值只可能为 $0,\ldots,M-1$，并且每个数值都有唯一后继。因此，从初值出发的轨迹一定由一条前导链和一个循环组成。设前导链长度为 $\mu$，循环长度为 $\lambda$，则

$$\mu+\lambda\le M.$$

这个方法依赖 $M$ 的大小，适合子任务 $3,4$。天数再大，也只需找出循环后对其长度取余。它不依赖逐天执行到第 $N$ 天，因此 $N$ 较小并不能弥补巨大 $M$ 带来的找环开销。

用 Floyd 算法求入口和长度

使用两个位置，都从初值出发。慢指针每次调用一次 $h$，快指针每次调用两次 $h$，直到相遇。进入循环后，两者相对速度为每轮一步，最终一定相遇。

设相遇时慢指针共走了 $q$ 步。两者的路程差为 $q$，故 $q$ 是 $\lambda$ 的倍数。将一个指针放回初值，另一个停在相遇点，两者每次都走一步：

• 重置的指针在 $\mu$ 步后第一次到达循环入口；
• 另一个指针此时相对入口的位置为 $q$，模 $\lambda$ 后也是 $0$。

所以它们再次相遇的地方就是入口，走过的步数就是 $\mu$。固定入口，让另一个指针走到再次回到入口，得到 $\lambda$。自环也包含在内，例如 $0\to0$ 的循环长度为 $1$。

还原第 N 天

总操作数为 $t=N-1$。若 $t<\mu$，目标仍在前导链上；否则可以替换为

$$t'=\mu+(t-\mu)\bmod\lambda.$$

从初值重新执行 $t'$ 步即可得到答案。重新走这一段不会超过前导链加一圈的长度，不需要保存全部历史数值。

例如 $A=14,M=25$ 时，$\mu=0,\lambda=12$。第 $115$ 天需要 $114$ 次更新，取余后只需更新 $6$ 次，得到 $16$。

时间复杂度为 $O(MD)$，其中 $D$ 是 $M-1$ 的十进制位数：寻找相遇点、入口、循环长度以及还原答案，都只行走 $O(\mu+\lambda)$ 次，每次提取数位花费 $O(D)$。空间复杂度为 $O(1)$。

参考代码（C++20）

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

void solve() {
  i64 a, mod, n;
  cin >> a >> mod >> n;
  n--;
  auto next_value = [&](i64 x) {
    int d = 0;
    for (i64 y = x; y > 0; y /= 10) d = max(d, (int)(y % 10));
    return (x + d) % mod;
  };
  i64 slow = next_value(a), fast = next_value(next_value(a));
  while (slow != fast) {
    slow = next_value(slow);
    fast = next_value(next_value(fast));
  }
  i64 pre = 0;
  slow = a;
  while (slow != fast) {
    slow = next_value(slow);
    fast = next_value(fast);
    pre++;
  }
  i64 len = 1;
  fast = next_value(slow);
  while (slow != fast) {
    fast = next_value(fast);
    len++;
  }
  if (n > pre) n = pre + (n - pre) % len;
  for (i64 i = 0; i < n; i++) a = next_value(a);
  cout << a << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

固定宽度数字块与循环节（通过子任务 1–4，共 65 分）

把连续数值分成固定宽度的块

这个方法覆盖子任务 $1$ 至 $4$：$N\le10^8$ 或 $M\le10^8$ 时，可以一次跳过一段逐步递增过程。

取 $B=10^5$，将数值分为

$$[qB,(q+1)B-1].$$

当前数写为 $qB+x$。没有跨块时，高位 $q$ 不变；记 $d=\operatorname{big}(q)$，每一步的增量就是

$$\max(d,\operatorname{big}(x)).$$

因此，不同的块可以共享一份以 $d,x$ 为下标的转移表。

预处理从任意后缀走出块

先求 $0\le x<B$ 的最大数位：

$$b(0)=0,\qquad b(x)=\max(b(\lfloor x/10\rfloor),x\bmod10).$$

定义

$$F(d,x)=(f(d,x),g(d,x)),$$

其中 $0\le d\le9$、$0\le x<B$。$f(d,x)$ 表示从后缀 $x$ 出发、第一次达到至少 $B$ 所需的步数，$g(d,x)$ 表示走出后的数值减去 $B$。

先执行一步，令

$$y=x+\max(d,b(x)).$$

则

$$F(d,x)= \begin{cases} (+\infty,0),&d=x=0,\\ (1,y-B),&y\ge B,\\ (1+f(d,y),g(d,y)),&y<B,\ (d,x)\ne(0,0). \end{cases}$$

非零状态均有 $y>x$，所以对每个 $d$ 按 $x$ 从大到小计算，依赖的状态已经求出。跨块时每步至多增加 $9$，故所有有效出口偏移均在 $0,\ldots,8$ 内。

这张表的后缀范围是全部 $0,\ldots,B-1$，所以原始起点在块中间时也能直接查询。

跳转与尾部模拟

令剩余操作数为 $t=N-1$。当前块左端点是 $l=\lfloor a/B\rfloor B$，查询 $F(\operatorname{big}(\lfloor a/B\rfloor),a\bmod B)$。

若 $l+B\le M$，且剩余步数足够走出当前块，就扣除表中的步数，并将当前值改为块尾之后的对应出口：

$$a\leftarrow l+B+g(d,x),\qquad t\leftarrow t-f(d,x).$$

若模数截断了当前块，或者剩余步数不足以走完，就只执行一次原始更新。这样既不会越过所求的天数，也不会把模数边界与数字块边界混淆。每次推进后对 $M$ 取模；若得到 $0$，后续恒为 $0$。

天数大时，在取模后找循环

每次跨过 $M$ 之后，数值只可能在 $0,\ldots,8$ 中，因为更新前至多 $M-1$，每次又至多加 $9$。

记录这些小数值出现时的剩余步数。同一个数值再次出现时，前后剩余步数之差 $L$ 就是一段真实循环的长度，可以将 $t$ 改为 $t\bmod L$。入口状态数是常数，因此在跳过重复循环后，只会完整经过常数个模区间。

这使算法同时利用两种限制：$N$ 较小时，总推进步数受 $N$ 限制；$M$ 较小时，完成少量模区间后即可跳过重复过程。

成本与适用范围

时间复杂度为 $O(10B+D(B+\min(N,M)/B))$，其中十进制相关常数视为常数，$D\le18$。预处理耗费 $O(10B)$。

每个完整块除第一次从中间进入的情况外，至少代表约 $B/9$ 次真实操作。因此，受限于 $N$ 或常数个模区间，总整块跳转次数为 $O(\min(N,M)/B+1)$。每个模区间最后不足一块的部分，以及最后不足以跳完整块的部分，合计只需 $O(B)$ 次逐步模拟。一次查询高位最大数位或逐步更新花费 $O(D)$。

空间复杂度为 $O(10B)$，保存全部后缀的步数与出口偏移。

当 $M,N$ 都达到 $10^{18}$ 时，即使每次跨过 $10^5$ 的数值范围，块数仍然过多。满分解需要把固定宽度扩展为多层十进制块。

参考代码（C++20）

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

int big(i64 x) {
  int d = 0;
  for (; x > 0; x /= 10) d = max(d, (int)(x % 10));
  return d;
}

void solve() {
  i64 a, mod, n;
  cin >> a >> mod >> n;
  n--;
  constexpr int base = 100000;
  vector<int> digit(base);
  for (int x = 1; x < base; x++) digit[x] = max(digit[x / 10], x % 10);
  using state = pair<int, int>;
  vector dp(10, vector<state>(base));
  for (int d = 0; d <= 9; d++) {
    for (int x = base - 1; x >= 0; x--) {
      if (d == 0 && x == 0) {
        dp[d][x] = {INT_MAX, 0};
        continue;
      }
      int y = x + max(d, digit[x]);
      if (y >= base) {
        dp[d][x] = {1, y - base};
      } else {
        auto [cnt, nxt] = dp[d][y];
        dp[d][x] = {cnt + 1, nxt};
      }
    }
  }
  vector<i64> first(9, -1);
  while (n > 0 && a != 0) {
    if (a <= 8) {
      if (first[a] != -1) {
        n %= first[a] - n;
        if (n == 0) break;
      }
      first[a] = n;
    }
    i64 l = a / base * base;
    auto [cnt, nxt] = dp[big(a / base)][a % base];
    if (l + base <= mod && cnt <= n) {
      a = l + base + nxt;
      n -= cnt;
    } else {
      a += big(a);
      n--;
    }
    a %= mod;
  }
  cout << a << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

逐天模拟（通过子任务 1，共 15 分）

当 $N\le10^6$ 时，直接执行每天的变化即可，覆盖子任务 $1$。

第 $1$ 天已经等于给定的 $A$，所以只执行 $N-1$ 次更新。每次复制当前数值，不断取末位并除以 $10$，求出最大的十进制数字，再将当前值加上它并对 $M$ 取模。

若当前值已经是 $0$，其最大数位也为 $0$，之后不再变化，可以提前结束。这个判断来自原转移，与天数大小无关。

例如，从 $14$ 开始、模数为 $25$ 时，先加最大数位 $4$ 得到 $18$，再加 $8$ 并取模得到 $1$。后续每天都应用同一规则。

每一步均严格执行题目定义，执行次数又恰为 $N-1$，所以最后的数值就是第 $N$ 天的答案。大天数下，即使数值重复，这种写法仍会逐步行走，不能处理一般的巨大 $N$。

时间复杂度为 $O(ND)$，其中 $D\le18$ 为当前值的最大十进制位数。空间复杂度为 $O(1)$。

参考代码（C++20）

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

void solve() {
  i64 a, mod, n;
  cin >> a >> mod >> n;
  for (i64 i = 1; i < n && a != 0; i++) {
    int d = 0;
    for (i64 x = a; x > 0; x /= 10) d = max(d, (int)(x % 10));
    a = (a + d) % mod;
  }
  cout << a << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}