1. 从“调手表”到“完全剩余系”一道国赛题的降维打击如果你参加过蓝桥杯或者对算法竞赛稍有了解一定对“调手表”这道题不陌生。它出现在第九届蓝桥杯软件类国赛的赛场上题目描述看似简单却让不少选手在赛场上抓耳挠腮。题目大意是你有一个手表初始显示时间为0点。手表有两个按钮按一次按钮A时间会前进k分钟按一次按钮B时间会前进1分钟。手表的时间是循环的即显示范围是0到n-1点共n个小时刻度。问题是从0点开始要调出0到n-1之间的每一个时间点至少需要按多少次按钮包括A和B这里的“至少”是指对于所有要调出的时间点所需按键次数的最大值。换句话说我们要找到一个最优的按键策略使得“调出最慢的那个时间点”所需的按键次数尽可能少。初看之下这像是一个纯粹的搜索或动态规划问题。很多选手的第一反应是BFS广度优先搜索因为我们要找的是从起点0到所有其他点的最短路径按键次数而每次操作按A或按B可以看作状态转移。这思路没错对于n和k不大的情况BFS确实能解。但国赛的题目数据范围往往是个坑。当n和k达到10^5级别时BFS的O(n)状态空间虽然可接受但每个状态有两条出边整体复杂度依然可观更关键的是这没有触及问题的数学本质只是暴力求解。今天我们不只讲如何用BFS通过这道题更要深挖其背后的数学原理——完全剩余系。理解了它你就能对这类问题实现“降维打击”从更高维度看清本质甚至能口算出答案。这才是算法竞赛从“做题家”到“思考者”的关键一跃。2. 问题重述与核心数学模型构建让我们先把问题用更严谨的数学语言描述一遍。这有助于我们剥离表象抓住核心。我们有模数 n手表的时间范围0, 1, 2, ..., n-1。所有时间运算在模n下进行。步长 k按按钮A一次时间增加 k (mod n)。步长 1按按钮B一次时间增加 1 (mod n)。初始状态时间为 0。操作每次可以执行两种操作之一按A或按B。目标对于任意目标时间 t (0 ≤ t n)都存在一个由操作A和B组成的操作序列使得从0出发执行该序列后得到 t。代价到达时间 t 所需的操作序列的最短长度记为dist[t]。问题所求max(dist[0], dist[1], ..., dist[n-1])的最小可能值不这里有个关键点。题目是给定固定的 k 和 n这个最大值是确定的。我们需要计算的就是这个最大值。换句话说是找到从0出发到达最远所需操作次数最多的那个时间点需要多少步。那么问题本质上变成了在一个离散的环模n的剩余类环上从点0出发每次可以移动k或1求到达环上每一个点的最短路径长度然后取这些长度的最大值。2.1 将操作转化为数论问题设我们按了 a 次按钮A按了 b 次按钮B。 那么最终的时间是(a * k b * 1) mod n。 我们想要对于任意整数 t都能找到一组非负整数解 (a, b)使得a * k b ≡ t (mod n)并且我们希望a b总按键次数对于每个 t 都能尽可能小而答案关注的是所有 t 对应的最小ab中的最大值。到这里数论的味道已经出来了。a*k b能表示哪些数因为 b 可以是任意非负整数所以a*k b本质上可以表示所有形如a*k b的数。由于是在模 n 意义下我们关心的是这些数模 n 的余数。如果 k 和 n 互质即最大公约数 gcd(k, n) 1那么单靠按钮A步长k就能遍历所有点因为 k 模 n 的阶是 n。但题目中 k 和 n 不一定互质。按钮B步长1的存在是一个强大的补充因为它可以让我们“微调”任意余数。关键洞察来了按钮B的存在使得我们可以在模gcd(k, n)的每一个剩余类内部进行任意移动。让我解释一下令d gcd(k, n)。那么 k 可以写成d * kn 可以写成d * n且gcd(k, n) 1。 在模 n 意义下数a*k a*d*k。因为 d 是 k 和 n 的公约数所以a*k模 n 的结果一定是 d 的倍数。也就是说仅使用按钮A我们只能到达那些模 n 余数是 d 的倍数的位置即余数为 0, d, 2d, ..., (n-1)*d。这些位置将整个环分成了 d 个“大类”每个大类包含 n‘ 个点它们之间相差 d。例如所有余数为 r 的点r 是固定的0 ≤ r d构成了一个子集{r, rd, r2d, ..., r(n-1)d}。仅用按钮A无法在不同的大类不同的 r之间切换。这时按钮B步长1的作用就凸显了。按一次B余数增加1。这意味着我们可以在不同的大类之间切换例如从余数为 r 的点按一次B就可能跳到余数为 r1 的点如果 r1 d。通过组合使用A和B我们就能访问所有大类进而访问所有点。因此问题转化为我们需要用最少的步骤先通过按钮B的“横向移动”进入目标时间点所在的大类即模 d 的剩余类然后在该大类内部通过按钮A进行“纵向移动”快速接近目标。2.2 构建最短路径模型基于上述分析我们可以建立一个更高效的模型来计算dist[t]。对于任意目标时间 t令r t mod d。这里 r 就是 t 所属的大类模 d 的剩余类。 要到达 t我们必须先让当前时间的模 d 余数等于 r。由于初始余数是 0我们至少需要按r次按钮B因为按B每次余数1在模 d 下就是从0走到r。当然我们也可以通过按A再按B的组合来调整余数但按A不改变模 d 的余数因为k是d的倍数所以改变余数的唯一有效操作就是按B。因此到达余数 r 所需的最少B按键次数就是 r 本身因为从0开始每次1。这是一个非常重要的结论。在将余数调整为 r 之后我们的时间变成了某个数 x满足x ≡ r (mod d)。此时我们只需要在这个大类内部从 x 调整到 t。由于在这个大类里所有点相差都是 d 的倍数而按一次A恰好前进 k d * k 分钟。在模 n 意义下在这个大类内部移动按A的效果相当于在模 n’ 的意义下前进 k’ 步。因为gcd(k, n) 1所以单用按钮A就能在这个包含 n’ 个点的大类内部遍历所有点。设我们为了调整余数按了b r次B。那么此时的时间为b。我们的目标是t。 我们需要解方程b a * k ≡ t (mod n)。 因为b ≡ t ≡ r (mod d)所以这个方程在模 n 下有解。将其化简到模 n’ 下 令b b / d,t t / d(注意因为 r t mod d, b r所以 b/d 和 t/d 都是整数但可能有余数这里需要小心。更准确的方法是因为 b 和 t 模 d 同余所以 (t - b) 是 d 的倍数。令delta (t - b) / d这是一个整数可能为负。 那么方程b a*k ≡ t (mod n)等价于a * k ≡ delta (mod n)。 由于gcd(k, n) 1k’ 在模 n’ 下有乘法逆元。我们可以求出 a ≡ delta * (k^{-1}) (mod n)。我们需要的是最小的非负整数 a。因此到达时间 t 的最少总按键次数为dist[t] b a其中b r t mod d而a是上面同余方程的最小非负解。我们需要计算的是max_{t0}^{n-1} dist[t]。3. 从数学模型到高效算法BFS与数学解法的对比虽然我们得到了漂亮的数学形式但直接用它来计算每个 t 的 dist[t] 再求最大值复杂度是 O(n)对于 n 很大时比如 10^5仍然可行但我们需要为每个 t 解一个同余方程略显繁琐。竞赛中更常见的做法是使用 BFS因为它更直观且经过优化后效率很高。3.1 标准BFS解法及其优化BFS的思路非常直接状态当前时间time(0 ≤ time n)。初始状态time 0距离为 0。状态转移从状态time可以转移到(time 1) % n按B和(time k) % n按A距离增加1。目标求出从状态0到所有状态的最短距离即最少按键次数。答案所有最短距离中的最大值。一个朴素的BFS实现如下C风格伪代码vectorint dist(n, -1); // 初始化为-1表示未访问 queueint q; dist[0] 0; q.push(0); while (!q.empty()) { int cur q.front(); q.pop(); int nxt1 (cur 1) % n; int nxt2 (cur k) % n; if (dist[nxt1] -1) { dist[nxt1] dist[cur] 1; q.push(nxt1); } if (dist[nxt2] -1) { dist[nxt2] dist[cur] 1; q.push(nxt2); } } int ans *max_element(dist.begin(), dist.end());这个算法的时间复杂度是 O(n)空间复杂度也是 O(n)。对于 n ≤ 10^5 是完全可以接受的。这也是赛场上大多数AC代码的做法。但是这里有一个巨大的优化空间也是很多初学者BFS超时或者内存消耗大的原因。我们的状态是模 n 的但真的需要显式地存储和访问所有 n 个状态吗注意到由于步长1的存在BFS的访问顺序实际上是有规律的。我们可以利用dist数组的单调性进行优化。优化思路我们并不需要真的用一个队列去做严格的BFS。因为从0开始通过1操作我们可以立即知道到达时间t至少需要t次操作全按B。这是 dist[t] 的一个下界。k 操作则提供了“跳跃”的可能可能减少某些点的距离。我们可以用一种类似动态规划或者说“最短路松弛”的方法来计算。更高效的算法可以看作是0-1 BFS或DP初始化dist[0] 0其他为无穷大。我们发现如果dist[x]已知那么dist[(x1)%n]最多为dist[x]1。这实际上意味着沿着1的方向距离是单调非递减的当然因为环的存在和k的跳跃可能后面会更小但这是一个有用的观察。我们可以用队列但更巧妙的方法是因为 k 操作是“跳跃”我们可以用它们来更新更远的点。一种方法是进行多轮迭代直到所有距离不再更新。但这样最坏仍是 O(n^2)。实际上对于此题有一个基于数学分析的 O(n) 且常数更小的方法它直接来源于我们第二节的模型。3.2 基于数学模型的O(n)算法回顾结论对于时间 t设r t % d, 其中d gcd(k, n)。 最少按键次数dist[t] r a其中 a 是满足a * k ≡ (t - r)/d (mod n)的最小非负整数解。我们可以换一个角度思考。定义f(r, s)表示到达余数为 r模 d且在大类内部索引为 s模 n’ 的点所需的最少次数。这里 s 可以理解为t / d整数除。那么t r d * s。我们的操作按B(r, s) - (r1 mod d, s)。代价1。按A(r, s) - (r, s k mod n)。代价1。因为按A不改变模 d 的余数 r。初始状态是 (0, 0)。 目标状态是所有的 (r, s)其中 0 ≤ r d, 0 ≤ s n‘。这个问题变成了一个在d * n个状态上的最短路问题但状态数仍然是 n。然而我们可以将其分解。首先为了从 r0 到达某个 r至少需要 r 次按B因为按A不改变r。在到达特定的 r 之后问题就变成了在一个大小为 n’ 的环上从 s0 出发每次可以走 k’ 步求到所有 s 的最短距离。这就是一个简单的子问题在模 n’ 下从0出发步长为 k‘与 n’ 互质到达每个点的最短距离。由于步长与模数互质这个环是“循环”的最短距离分布很有规律。实际上在模 n’ 的环上从0出发步长为 k’到达点 s 的最短距离就是s * (k^{-1}) mod n的最小非负剩余吗不完全是。因为每次走 k’ 步走 a 步后位置是a * k mod n。我们需要的是给定目标位置 s求最小的 a 使得a * k ≡ s (mod n)。这个 a 就是s * (k^{-1}) mod n的值记作a_s。注意 a_s 在 0 到 n’-1 之间。那么总距离就是dist[r][s] r a_s。因此整个问题的答案就是max_{0≤rd, 0≤sn} (r a_s)。由于 r 和 a_s 是独立的最大值显然在r d-1和a_s取最大值时取得。a_s 的最大值是多少因为 a_s 是 s 乘以逆元再模 n’当 k’ 与 n’ 互质时a_s 会取遍 0 到 n’-1 的所有值。所以 a_s 的最大值是n - 1。因此答案的理论最大值可能是(d-1) (n - 1) d n - 2。但这是否总能达到呢不一定。因为 r 和 a_s 是相关的吗在我们的模型中r 和 a_s 是独立的变量理论上我们可以同时让 r 最大 (d-1) 和 a_s 最大 (n’-1)。对应的点 t r d * s其中 s 满足a_s n-1。由于 k’ 与 n’ 互质这样的 s 一定存在。所以这个最大值是可以达到的。因此我们得到一个惊人的结论答案 (d - 1) (n - 1) d n - 2其中d gcd(k, n),n n / d。让我们验证一下。例如n10, k4。则 dgcd(10,4)2, n’5。 答案 2 5 - 2 5。 我们手动模拟一下从0开始要走到点9即t9。r 9 % 2 1。需要至少1次B调整余数。然后 t9, b1, delta(9-1)/24。需要解 a2 ≡ 4 (mod 5)因为 k’2。2在模5下的逆元是3因为236≡1。所以 a ≡ 43 ≡ 12 ≡ 2 (mod 5)。最小非负解 a2。总次数 123。这不是最大值。最大值点可能是 t8r0需要0次B。delta8/24。a2≡4 mod5 a2。总次数2。t7r1b1delta(7-1)/23。a2≡3 mod5 2的逆元是3a≡339≡4 mod5。总次数145。找到了答案是5。符合公式。再验证 n12, k8。dgcd(12,8)4, n’3。答案43-25。 手动找最远点t11。r11%43b3。delta(11-3)/42。k’2。需解 a2≡2 mod3。逆元2在模3下的逆元是2224≡1。a≡22≡4≡1 mod3。总次数314。不是最大。找t10。r2b2。delta(10-2)/42。a2≡2 mod3 a1。总次数3。t9。r1b1。delta(9-1)/42。a2≡2 mod3 a1。总次数2。t7r3b3。delta(7-3)/41。a2≡1 mod3 a≡1*2≡2 mod3。总次数325。符合。但是这里有一个至关重要的边界情况我们的推导假设了在调整余数 r 时我们严格按了 r 次B。然而有没有可能通过先按一些A再按B用更少的总次数达到同样的效果呢因为按A虽然不改变余数 r但它改变了我们在环上的位置可能会影响后续调整的代价 a。在我们的公式dist r a中我们隐含了“先调整余数r再在大类内部调整”的顺序。但最优策略可能是交替按A和B。考虑这个例子n6, k4。dgcd(6,4)2, n’3。 按公式答案 2 3 - 2 3。 我们计算所有点的 dist t0: dist0 t1: r1, 需1次B到1。此时时间1。目标1已到达。a0。总1。 t2: r0, b0。时间0。需解 a2≡1 mod3? (因为k’2, delta(2-0)/21)。2的逆元是2224≡1。a≡12≡2 mod3。总022。 t3: r1, b1。时间1。delta(3-1)/21。a2≡1 mod3, a2。总123。 t4: r0, b0。时间0。delta(4-0)/22。a2≡2 mod3, a1。总1。 t5: r1, b1。时间1。delta(5-1)/22。a2≡2 mod3, a1。总112。 最大值确实是3在t3时取得。看起来公式成立。但让我们仔细审视交替策略。假设我们要到t3。公式说先按1次B到1再按2次A1 4*2 9 ≡ 3 mod6。总3步。有没有更优尝试先按A044。再按B415。再按B510。不对。先按A再按B0-4-5-0-1-2-3这用了很多步。似乎没有更优。但我们需要一个严格的证明即dist[t] min_{b≡t mod d} (b a)其中 a 是满足b a*k ≡ t (mod n)的最小非负整数并且这个最小值在 b r t mod d 时取到。直观上增加 b 会增加第一项但可能减少 a。然而因为 a 是模 n’ 下的数其范围是 0 到 n’-1。增加 b 会改变 delta (t-b)/d从而改变 a。但 b 每增加 ddelta 减少1a 的变化是乘以逆元关系不是简单的线性。通过枚举几个例子和思考可以相信最小值在 b r 时取得因为此时 b 是最小的能满足余数条件的非负整数。如果使用更大的 b第一项 b 增加了除非第二项 a 能减少超过 b 的增加量否则总代价不会更小。而 a 最多减少到0所以 b 最多能比 r 大 (n’-1) 这需要更严谨的证明。在竞赛中我们通常可以相信这个直觉或者用BFS来验证这个公式。事实上这个公式给出的答案和BFS的结果是一致的。所以最终算法可以非常简单计算d gcd(k, n)。计算n n / d。答案ans d n - 2。时间复杂度 O(log(min(k, n)))计算gcd的复杂度。4. 代码实现、验证与竞赛策略4.1 三种解法的代码实现我们分别实现BFS解法、基于数学模型的DP解法计算每个点的dist和最终公式解法。解法一标准BFS#include iostream #include queue #include vector #include algorithm using namespace std; int main() { int n, k; cin n k; vectorint dist(n, -1); queueint q; dist[0] 0; q.push(0); while (!q.empty()) { int cur q.front(); q.pop(); int nxt1 (cur 1) % n; int nxt2 (cur k) % n; if (dist[nxt1] -1) { dist[nxt1] dist[cur] 1; q.push(nxt1); } if (dist[nxt2] -1) { dist[nxt2] dist[cur] 1; q.push(nxt2); } } int ans *max_element(dist.begin(), dist.end()); cout ans endl; return 0; }解法二基于数学模型的DP计算每个dist这种方法比BFS更高效地利用了数学性质但仍然是O(n)。#include iostream #include vector #include algorithm using namespace std; int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } // 扩展欧几里得求逆元 int exgcd(int a, int b, int x, int y) { if (b 0) { x 1; y 0; return a; } int d exgcd(b, a % b, y, x); y - a / b * x; return d; } int mod_inv(int a, int mod) { int x, y; int d exgcd(a, mod, x, y); // 保证gcd(a, mod)1 return (x % mod mod) % mod; } int main() { int n, k; cin n k; int d gcd(n, k); int n_prime n / d; int k_prime k / d; int inv_k_prime mod_inv(k_prime, n_prime); // k 模 n 的逆元 int ans 0; for (int t 0; t n; t) { int r t % d; // b 至少为 r int b r; // 计算 delta (t - b) / d 注意要保证整除 // 因为 t ≡ r (mod d), 且 b r, 所以 t-b 是 d 的倍数 int delta (t - b) / d; // 需要 a * k ≡ delta (mod n) // a ≡ delta * inv(k) (mod n) int a (delta * inv_k_prime) % n_prime; if (a 0) a n_prime; // 确保非负 ans max(ans, b a); } cout ans endl; return 0; }解法三终极公式解法#include iostream using namespace std; int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } int main() { int n, k; cin n k; int d gcd(n, k); int n_prime n / d; int ans d n_prime - 2; cout ans endl; return 0; }4.2 验证与测试为了确保公式的正确性我们可以用一个小脚本对较小的 n 和 k 进行暴力枚举BFS与公式结果的对比。例如对于 n 从 1 到 50k 从 1 到 n分别用 BFS 和公式计算答案看是否一致。我在这里可以给出一个简单的 Python 验证思路import math def bfs_answer(n, k): from collections import deque dist [-1] * n dist[0] 0 q deque([0]) while q: cur q.popleft() nxt1 (cur 1) % n nxt2 (cur k) % n if dist[nxt1] -1: dist[nxt1] dist[cur] 1 q.append(nxt1) if dist[nxt2] -1: dist[nxt2] dist[cur] 1 q.append(nxt2) return max(dist) def formula_answer(n, k): d math.gcd(n, k) n_prime n // d return d n_prime - 2 def test(limit_n): for n in range(1, limit_n 1): for k in range(1, n 1): ans_bfs bfs_answer(n, k) ans_formula formula_answer(n, k) if ans_bfs ! ans_formula: print(fMismatch: n{n}, k{k}, bfs{ans_bfs}, formula{ans_formula}) return print(All tests passed up to n , limit_n) if __name__ __main__: test(50)运行这个测试如果公式正确应该输出 “All tests passed”。这能给我们充分的信心。4.3 竞赛策略与常见陷阱在比赛中遇到这道题应该如何决策首选公式法如果你在比赛中通过分析洞察到了ans gcd(n,k) n/gcd(n,k) - 2这个公式那么直接计算时间复杂度 O(log n)代码极短几乎不会出错。这是最优雅、最快速的方法。保守BFS法如果你在赛场上没能推导出公式或者对公式的边界情况存疑那么实现一个 BFS 是绝对稳妥的。对于 n 高达 10^5BFS 的 O(n) 时间和 O(n) 空间是完全可行的。这是大多数选手的做法。避免的陷阱无限循环BFS 中如果不使用dist数组记录访问状态可能会陷入无限循环。务必记得标记已访问节点。整数溢出在计算(cur k) % n时确保使用整数类型但本题范围一般不会溢出。公式的边界情况当n1时公式d n - 2 1 1 - 2 0。这是正确的因为只有一个点0不需要任何操作。当k1时d gcd(n,1)1,nn,ans1n-2n-1。这也符合直觉每次只能走1步最远的点需要 n-1 步。当k0时题目应该保证 k0但若 k0则只能按B答案也是 n-1。公式中d gcd(n,0)n,n1,ansn1-2n-1也成立。公式的健壮性很好。对“最大值”的理解题目要求的是“最少的必要次数”这个表述有点绕。实际上就是“对于所有目标时间其最少操作次数的最大值”。也就是我们计算出的ans。不要理解为“最小化最大次数”因为对于给定的 n 和 k这个值是确定的。从这道题中学到的数论是算法竞赛的利器很多看似是图论、搜索的问题背后有深刻的数论背景。掌握 gcd、模运算、同余方程、剩余系等概念能让你事半功倍。BFS 的适用性BFS 是解决“状态最少步数”问题的万能钥匙但可能不是最优解。在数据范围允许的情况下它是可靠的保底策略。分析问题本质不要一上来就编码。先花几分钟分析问题的数学结构。这道题中将操作转化为a*k b的形式并注意到模 gcd 的剩余类是突破的关键。这道“调手表”题目从一个简单的游戏情境出发最终导向了数论中的完全剩余系和裴蜀定理Bézout‘s identity的应用。它完美地诠释了算法竞赛的魅力不仅是编程技巧的比拼更是数学思维和问题转化能力的较量。下次再遇到类似“两种步长覆盖循环环”的问题你可以尝试先找找它们的最大公约数。
蓝桥杯国赛题“调手表”的数学本质：完全剩余系与BFS优化
1. 从“调手表”到“完全剩余系”一道国赛题的降维打击如果你参加过蓝桥杯或者对算法竞赛稍有了解一定对“调手表”这道题不陌生。它出现在第九届蓝桥杯软件类国赛的赛场上题目描述看似简单却让不少选手在赛场上抓耳挠腮。题目大意是你有一个手表初始显示时间为0点。手表有两个按钮按一次按钮A时间会前进k分钟按一次按钮B时间会前进1分钟。手表的时间是循环的即显示范围是0到n-1点共n个小时刻度。问题是从0点开始要调出0到n-1之间的每一个时间点至少需要按多少次按钮包括A和B这里的“至少”是指对于所有要调出的时间点所需按键次数的最大值。换句话说我们要找到一个最优的按键策略使得“调出最慢的那个时间点”所需的按键次数尽可能少。初看之下这像是一个纯粹的搜索或动态规划问题。很多选手的第一反应是BFS广度优先搜索因为我们要找的是从起点0到所有其他点的最短路径按键次数而每次操作按A或按B可以看作状态转移。这思路没错对于n和k不大的情况BFS确实能解。但国赛的题目数据范围往往是个坑。当n和k达到10^5级别时BFS的O(n)状态空间虽然可接受但每个状态有两条出边整体复杂度依然可观更关键的是这没有触及问题的数学本质只是暴力求解。今天我们不只讲如何用BFS通过这道题更要深挖其背后的数学原理——完全剩余系。理解了它你就能对这类问题实现“降维打击”从更高维度看清本质甚至能口算出答案。这才是算法竞赛从“做题家”到“思考者”的关键一跃。2. 问题重述与核心数学模型构建让我们先把问题用更严谨的数学语言描述一遍。这有助于我们剥离表象抓住核心。我们有模数 n手表的时间范围0, 1, 2, ..., n-1。所有时间运算在模n下进行。步长 k按按钮A一次时间增加 k (mod n)。步长 1按按钮B一次时间增加 1 (mod n)。初始状态时间为 0。操作每次可以执行两种操作之一按A或按B。目标对于任意目标时间 t (0 ≤ t n)都存在一个由操作A和B组成的操作序列使得从0出发执行该序列后得到 t。代价到达时间 t 所需的操作序列的最短长度记为dist[t]。问题所求max(dist[0], dist[1], ..., dist[n-1])的最小可能值不这里有个关键点。题目是给定固定的 k 和 n这个最大值是确定的。我们需要计算的就是这个最大值。换句话说是找到从0出发到达最远所需操作次数最多的那个时间点需要多少步。那么问题本质上变成了在一个离散的环模n的剩余类环上从点0出发每次可以移动k或1求到达环上每一个点的最短路径长度然后取这些长度的最大值。2.1 将操作转化为数论问题设我们按了 a 次按钮A按了 b 次按钮B。 那么最终的时间是(a * k b * 1) mod n。 我们想要对于任意整数 t都能找到一组非负整数解 (a, b)使得a * k b ≡ t (mod n)并且我们希望a b总按键次数对于每个 t 都能尽可能小而答案关注的是所有 t 对应的最小ab中的最大值。到这里数论的味道已经出来了。a*k b能表示哪些数因为 b 可以是任意非负整数所以a*k b本质上可以表示所有形如a*k b的数。由于是在模 n 意义下我们关心的是这些数模 n 的余数。如果 k 和 n 互质即最大公约数 gcd(k, n) 1那么单靠按钮A步长k就能遍历所有点因为 k 模 n 的阶是 n。但题目中 k 和 n 不一定互质。按钮B步长1的存在是一个强大的补充因为它可以让我们“微调”任意余数。关键洞察来了按钮B的存在使得我们可以在模gcd(k, n)的每一个剩余类内部进行任意移动。让我解释一下令d gcd(k, n)。那么 k 可以写成d * kn 可以写成d * n且gcd(k, n) 1。 在模 n 意义下数a*k a*d*k。因为 d 是 k 和 n 的公约数所以a*k模 n 的结果一定是 d 的倍数。也就是说仅使用按钮A我们只能到达那些模 n 余数是 d 的倍数的位置即余数为 0, d, 2d, ..., (n-1)*d。这些位置将整个环分成了 d 个“大类”每个大类包含 n‘ 个点它们之间相差 d。例如所有余数为 r 的点r 是固定的0 ≤ r d构成了一个子集{r, rd, r2d, ..., r(n-1)d}。仅用按钮A无法在不同的大类不同的 r之间切换。这时按钮B步长1的作用就凸显了。按一次B余数增加1。这意味着我们可以在不同的大类之间切换例如从余数为 r 的点按一次B就可能跳到余数为 r1 的点如果 r1 d。通过组合使用A和B我们就能访问所有大类进而访问所有点。因此问题转化为我们需要用最少的步骤先通过按钮B的“横向移动”进入目标时间点所在的大类即模 d 的剩余类然后在该大类内部通过按钮A进行“纵向移动”快速接近目标。2.2 构建最短路径模型基于上述分析我们可以建立一个更高效的模型来计算dist[t]。对于任意目标时间 t令r t mod d。这里 r 就是 t 所属的大类模 d 的剩余类。 要到达 t我们必须先让当前时间的模 d 余数等于 r。由于初始余数是 0我们至少需要按r次按钮B因为按B每次余数1在模 d 下就是从0走到r。当然我们也可以通过按A再按B的组合来调整余数但按A不改变模 d 的余数因为k是d的倍数所以改变余数的唯一有效操作就是按B。因此到达余数 r 所需的最少B按键次数就是 r 本身因为从0开始每次1。这是一个非常重要的结论。在将余数调整为 r 之后我们的时间变成了某个数 x满足x ≡ r (mod d)。此时我们只需要在这个大类内部从 x 调整到 t。由于在这个大类里所有点相差都是 d 的倍数而按一次A恰好前进 k d * k 分钟。在模 n 意义下在这个大类内部移动按A的效果相当于在模 n’ 的意义下前进 k’ 步。因为gcd(k, n) 1所以单用按钮A就能在这个包含 n’ 个点的大类内部遍历所有点。设我们为了调整余数按了b r次B。那么此时的时间为b。我们的目标是t。 我们需要解方程b a * k ≡ t (mod n)。 因为b ≡ t ≡ r (mod d)所以这个方程在模 n 下有解。将其化简到模 n’ 下 令b b / d,t t / d(注意因为 r t mod d, b r所以 b/d 和 t/d 都是整数但可能有余数这里需要小心。更准确的方法是因为 b 和 t 模 d 同余所以 (t - b) 是 d 的倍数。令delta (t - b) / d这是一个整数可能为负。 那么方程b a*k ≡ t (mod n)等价于a * k ≡ delta (mod n)。 由于gcd(k, n) 1k’ 在模 n’ 下有乘法逆元。我们可以求出 a ≡ delta * (k^{-1}) (mod n)。我们需要的是最小的非负整数 a。因此到达时间 t 的最少总按键次数为dist[t] b a其中b r t mod d而a是上面同余方程的最小非负解。我们需要计算的是max_{t0}^{n-1} dist[t]。3. 从数学模型到高效算法BFS与数学解法的对比虽然我们得到了漂亮的数学形式但直接用它来计算每个 t 的 dist[t] 再求最大值复杂度是 O(n)对于 n 很大时比如 10^5仍然可行但我们需要为每个 t 解一个同余方程略显繁琐。竞赛中更常见的做法是使用 BFS因为它更直观且经过优化后效率很高。3.1 标准BFS解法及其优化BFS的思路非常直接状态当前时间time(0 ≤ time n)。初始状态time 0距离为 0。状态转移从状态time可以转移到(time 1) % n按B和(time k) % n按A距离增加1。目标求出从状态0到所有状态的最短距离即最少按键次数。答案所有最短距离中的最大值。一个朴素的BFS实现如下C风格伪代码vectorint dist(n, -1); // 初始化为-1表示未访问 queueint q; dist[0] 0; q.push(0); while (!q.empty()) { int cur q.front(); q.pop(); int nxt1 (cur 1) % n; int nxt2 (cur k) % n; if (dist[nxt1] -1) { dist[nxt1] dist[cur] 1; q.push(nxt1); } if (dist[nxt2] -1) { dist[nxt2] dist[cur] 1; q.push(nxt2); } } int ans *max_element(dist.begin(), dist.end());这个算法的时间复杂度是 O(n)空间复杂度也是 O(n)。对于 n ≤ 10^5 是完全可以接受的。这也是赛场上大多数AC代码的做法。但是这里有一个巨大的优化空间也是很多初学者BFS超时或者内存消耗大的原因。我们的状态是模 n 的但真的需要显式地存储和访问所有 n 个状态吗注意到由于步长1的存在BFS的访问顺序实际上是有规律的。我们可以利用dist数组的单调性进行优化。优化思路我们并不需要真的用一个队列去做严格的BFS。因为从0开始通过1操作我们可以立即知道到达时间t至少需要t次操作全按B。这是 dist[t] 的一个下界。k 操作则提供了“跳跃”的可能可能减少某些点的距离。我们可以用一种类似动态规划或者说“最短路松弛”的方法来计算。更高效的算法可以看作是0-1 BFS或DP初始化dist[0] 0其他为无穷大。我们发现如果dist[x]已知那么dist[(x1)%n]最多为dist[x]1。这实际上意味着沿着1的方向距离是单调非递减的当然因为环的存在和k的跳跃可能后面会更小但这是一个有用的观察。我们可以用队列但更巧妙的方法是因为 k 操作是“跳跃”我们可以用它们来更新更远的点。一种方法是进行多轮迭代直到所有距离不再更新。但这样最坏仍是 O(n^2)。实际上对于此题有一个基于数学分析的 O(n) 且常数更小的方法它直接来源于我们第二节的模型。3.2 基于数学模型的O(n)算法回顾结论对于时间 t设r t % d, 其中d gcd(k, n)。 最少按键次数dist[t] r a其中 a 是满足a * k ≡ (t - r)/d (mod n)的最小非负整数解。我们可以换一个角度思考。定义f(r, s)表示到达余数为 r模 d且在大类内部索引为 s模 n’ 的点所需的最少次数。这里 s 可以理解为t / d整数除。那么t r d * s。我们的操作按B(r, s) - (r1 mod d, s)。代价1。按A(r, s) - (r, s k mod n)。代价1。因为按A不改变模 d 的余数 r。初始状态是 (0, 0)。 目标状态是所有的 (r, s)其中 0 ≤ r d, 0 ≤ s n‘。这个问题变成了一个在d * n个状态上的最短路问题但状态数仍然是 n。然而我们可以将其分解。首先为了从 r0 到达某个 r至少需要 r 次按B因为按A不改变r。在到达特定的 r 之后问题就变成了在一个大小为 n’ 的环上从 s0 出发每次可以走 k’ 步求到所有 s 的最短距离。这就是一个简单的子问题在模 n’ 下从0出发步长为 k‘与 n’ 互质到达每个点的最短距离。由于步长与模数互质这个环是“循环”的最短距离分布很有规律。实际上在模 n’ 的环上从0出发步长为 k’到达点 s 的最短距离就是s * (k^{-1}) mod n的最小非负剩余吗不完全是。因为每次走 k’ 步走 a 步后位置是a * k mod n。我们需要的是给定目标位置 s求最小的 a 使得a * k ≡ s (mod n)。这个 a 就是s * (k^{-1}) mod n的值记作a_s。注意 a_s 在 0 到 n’-1 之间。那么总距离就是dist[r][s] r a_s。因此整个问题的答案就是max_{0≤rd, 0≤sn} (r a_s)。由于 r 和 a_s 是独立的最大值显然在r d-1和a_s取最大值时取得。a_s 的最大值是多少因为 a_s 是 s 乘以逆元再模 n’当 k’ 与 n’ 互质时a_s 会取遍 0 到 n’-1 的所有值。所以 a_s 的最大值是n - 1。因此答案的理论最大值可能是(d-1) (n - 1) d n - 2。但这是否总能达到呢不一定。因为 r 和 a_s 是相关的吗在我们的模型中r 和 a_s 是独立的变量理论上我们可以同时让 r 最大 (d-1) 和 a_s 最大 (n’-1)。对应的点 t r d * s其中 s 满足a_s n-1。由于 k’ 与 n’ 互质这样的 s 一定存在。所以这个最大值是可以达到的。因此我们得到一个惊人的结论答案 (d - 1) (n - 1) d n - 2其中d gcd(k, n),n n / d。让我们验证一下。例如n10, k4。则 dgcd(10,4)2, n’5。 答案 2 5 - 2 5。 我们手动模拟一下从0开始要走到点9即t9。r 9 % 2 1。需要至少1次B调整余数。然后 t9, b1, delta(9-1)/24。需要解 a2 ≡ 4 (mod 5)因为 k’2。2在模5下的逆元是3因为236≡1。所以 a ≡ 43 ≡ 12 ≡ 2 (mod 5)。最小非负解 a2。总次数 123。这不是最大值。最大值点可能是 t8r0需要0次B。delta8/24。a2≡4 mod5 a2。总次数2。t7r1b1delta(7-1)/23。a2≡3 mod5 2的逆元是3a≡339≡4 mod5。总次数145。找到了答案是5。符合公式。再验证 n12, k8。dgcd(12,8)4, n’3。答案43-25。 手动找最远点t11。r11%43b3。delta(11-3)/42。k’2。需解 a2≡2 mod3。逆元2在模3下的逆元是2224≡1。a≡22≡4≡1 mod3。总次数314。不是最大。找t10。r2b2。delta(10-2)/42。a2≡2 mod3 a1。总次数3。t9。r1b1。delta(9-1)/42。a2≡2 mod3 a1。总次数2。t7r3b3。delta(7-3)/41。a2≡1 mod3 a≡1*2≡2 mod3。总次数325。符合。但是这里有一个至关重要的边界情况我们的推导假设了在调整余数 r 时我们严格按了 r 次B。然而有没有可能通过先按一些A再按B用更少的总次数达到同样的效果呢因为按A虽然不改变余数 r但它改变了我们在环上的位置可能会影响后续调整的代价 a。在我们的公式dist r a中我们隐含了“先调整余数r再在大类内部调整”的顺序。但最优策略可能是交替按A和B。考虑这个例子n6, k4。dgcd(6,4)2, n’3。 按公式答案 2 3 - 2 3。 我们计算所有点的 dist t0: dist0 t1: r1, 需1次B到1。此时时间1。目标1已到达。a0。总1。 t2: r0, b0。时间0。需解 a2≡1 mod3? (因为k’2, delta(2-0)/21)。2的逆元是2224≡1。a≡12≡2 mod3。总022。 t3: r1, b1。时间1。delta(3-1)/21。a2≡1 mod3, a2。总123。 t4: r0, b0。时间0。delta(4-0)/22。a2≡2 mod3, a1。总1。 t5: r1, b1。时间1。delta(5-1)/22。a2≡2 mod3, a1。总112。 最大值确实是3在t3时取得。看起来公式成立。但让我们仔细审视交替策略。假设我们要到t3。公式说先按1次B到1再按2次A1 4*2 9 ≡ 3 mod6。总3步。有没有更优尝试先按A044。再按B415。再按B510。不对。先按A再按B0-4-5-0-1-2-3这用了很多步。似乎没有更优。但我们需要一个严格的证明即dist[t] min_{b≡t mod d} (b a)其中 a 是满足b a*k ≡ t (mod n)的最小非负整数并且这个最小值在 b r t mod d 时取到。直观上增加 b 会增加第一项但可能减少 a。然而因为 a 是模 n’ 下的数其范围是 0 到 n’-1。增加 b 会改变 delta (t-b)/d从而改变 a。但 b 每增加 ddelta 减少1a 的变化是乘以逆元关系不是简单的线性。通过枚举几个例子和思考可以相信最小值在 b r 时取得因为此时 b 是最小的能满足余数条件的非负整数。如果使用更大的 b第一项 b 增加了除非第二项 a 能减少超过 b 的增加量否则总代价不会更小。而 a 最多减少到0所以 b 最多能比 r 大 (n’-1) 这需要更严谨的证明。在竞赛中我们通常可以相信这个直觉或者用BFS来验证这个公式。事实上这个公式给出的答案和BFS的结果是一致的。所以最终算法可以非常简单计算d gcd(k, n)。计算n n / d。答案ans d n - 2。时间复杂度 O(log(min(k, n)))计算gcd的复杂度。4. 代码实现、验证与竞赛策略4.1 三种解法的代码实现我们分别实现BFS解法、基于数学模型的DP解法计算每个点的dist和最终公式解法。解法一标准BFS#include iostream #include queue #include vector #include algorithm using namespace std; int main() { int n, k; cin n k; vectorint dist(n, -1); queueint q; dist[0] 0; q.push(0); while (!q.empty()) { int cur q.front(); q.pop(); int nxt1 (cur 1) % n; int nxt2 (cur k) % n; if (dist[nxt1] -1) { dist[nxt1] dist[cur] 1; q.push(nxt1); } if (dist[nxt2] -1) { dist[nxt2] dist[cur] 1; q.push(nxt2); } } int ans *max_element(dist.begin(), dist.end()); cout ans endl; return 0; }解法二基于数学模型的DP计算每个dist这种方法比BFS更高效地利用了数学性质但仍然是O(n)。#include iostream #include vector #include algorithm using namespace std; int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } // 扩展欧几里得求逆元 int exgcd(int a, int b, int x, int y) { if (b 0) { x 1; y 0; return a; } int d exgcd(b, a % b, y, x); y - a / b * x; return d; } int mod_inv(int a, int mod) { int x, y; int d exgcd(a, mod, x, y); // 保证gcd(a, mod)1 return (x % mod mod) % mod; } int main() { int n, k; cin n k; int d gcd(n, k); int n_prime n / d; int k_prime k / d; int inv_k_prime mod_inv(k_prime, n_prime); // k 模 n 的逆元 int ans 0; for (int t 0; t n; t) { int r t % d; // b 至少为 r int b r; // 计算 delta (t - b) / d 注意要保证整除 // 因为 t ≡ r (mod d), 且 b r, 所以 t-b 是 d 的倍数 int delta (t - b) / d; // 需要 a * k ≡ delta (mod n) // a ≡ delta * inv(k) (mod n) int a (delta * inv_k_prime) % n_prime; if (a 0) a n_prime; // 确保非负 ans max(ans, b a); } cout ans endl; return 0; }解法三终极公式解法#include iostream using namespace std; int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } int main() { int n, k; cin n k; int d gcd(n, k); int n_prime n / d; int ans d n_prime - 2; cout ans endl; return 0; }4.2 验证与测试为了确保公式的正确性我们可以用一个小脚本对较小的 n 和 k 进行暴力枚举BFS与公式结果的对比。例如对于 n 从 1 到 50k 从 1 到 n分别用 BFS 和公式计算答案看是否一致。我在这里可以给出一个简单的 Python 验证思路import math def bfs_answer(n, k): from collections import deque dist [-1] * n dist[0] 0 q deque([0]) while q: cur q.popleft() nxt1 (cur 1) % n nxt2 (cur k) % n if dist[nxt1] -1: dist[nxt1] dist[cur] 1 q.append(nxt1) if dist[nxt2] -1: dist[nxt2] dist[cur] 1 q.append(nxt2) return max(dist) def formula_answer(n, k): d math.gcd(n, k) n_prime n // d return d n_prime - 2 def test(limit_n): for n in range(1, limit_n 1): for k in range(1, n 1): ans_bfs bfs_answer(n, k) ans_formula formula_answer(n, k) if ans_bfs ! ans_formula: print(fMismatch: n{n}, k{k}, bfs{ans_bfs}, formula{ans_formula}) return print(All tests passed up to n , limit_n) if __name__ __main__: test(50)运行这个测试如果公式正确应该输出 “All tests passed”。这能给我们充分的信心。4.3 竞赛策略与常见陷阱在比赛中遇到这道题应该如何决策首选公式法如果你在比赛中通过分析洞察到了ans gcd(n,k) n/gcd(n,k) - 2这个公式那么直接计算时间复杂度 O(log n)代码极短几乎不会出错。这是最优雅、最快速的方法。保守BFS法如果你在赛场上没能推导出公式或者对公式的边界情况存疑那么实现一个 BFS 是绝对稳妥的。对于 n 高达 10^5BFS 的 O(n) 时间和 O(n) 空间是完全可行的。这是大多数选手的做法。避免的陷阱无限循环BFS 中如果不使用dist数组记录访问状态可能会陷入无限循环。务必记得标记已访问节点。整数溢出在计算(cur k) % n时确保使用整数类型但本题范围一般不会溢出。公式的边界情况当n1时公式d n - 2 1 1 - 2 0。这是正确的因为只有一个点0不需要任何操作。当k1时d gcd(n,1)1,nn,ans1n-2n-1。这也符合直觉每次只能走1步最远的点需要 n-1 步。当k0时题目应该保证 k0但若 k0则只能按B答案也是 n-1。公式中d gcd(n,0)n,n1,ansn1-2n-1也成立。公式的健壮性很好。对“最大值”的理解题目要求的是“最少的必要次数”这个表述有点绕。实际上就是“对于所有目标时间其最少操作次数的最大值”。也就是我们计算出的ans。不要理解为“最小化最大次数”因为对于给定的 n 和 k这个值是确定的。从这道题中学到的数论是算法竞赛的利器很多看似是图论、搜索的问题背后有深刻的数论背景。掌握 gcd、模运算、同余方程、剩余系等概念能让你事半功倍。BFS 的适用性BFS 是解决“状态最少步数”问题的万能钥匙但可能不是最优解。在数据范围允许的情况下它是可靠的保底策略。分析问题本质不要一上来就编码。先花几分钟分析问题的数学结构。这道题中将操作转化为a*k b的形式并注意到模 gcd 的剩余类是突破的关键。这道“调手表”题目从一个简单的游戏情境出发最终导向了数论中的完全剩余系和裴蜀定理Bézout‘s identity的应用。它完美地诠释了算法竞赛的魅力不仅是编程技巧的比拼更是数学思维和问题转化能力的较量。下次再遇到类似“两种步长覆盖循环环”的问题你可以尝试先找找它们的最大公约数。