数位倍数这题我第一次看题目名以为又是一道暴力枚举倍数的水题。上手试了才意识到事情没那么简单。随便拿 n19 来说19 的数位和是 10不合格38 的数位和是 11不合格57 的数位和是 12不合格76、95、114、133……我把前十个倍数全列了一遍没有一个是数位和为 19 的倍数。而且致命的是你根本不知道要试到哪一项才能停手因为“最小”这两个字逼你必须按顺序全部查一遍。后来我换了个思路不枚举倍数而是枚举“数可以长成什么样”先让数字天生满足数位和是 n 的倍数再去筛数值是不是 n 的倍数。这篇文章记录的就是这个思路的完整展开候选数字集合怎么选、同余 BFS 的状态怎么设计、完整代码怎么写以及我在实现过程中踩过的坑。适合正在准备蓝桥杯、又不太熟悉“同余 BFS”这类题型的同学Java 选手也完全可以用同样的模型去写。1. 题目在问什么两个约束同时成立的最小正整数1.1 形式化数值倍数和数位和倍数题目描述一句话就能说完给定正整数 n找一个最小的正整数 m使得下面两个条件同时成立。m 是 n 的倍数也就是m % n 0m 的十进制数位和也是 n 的倍数也就是digitSum(m) % n 0注意“数位和”不是 m 本身是每一位数字加起来。比如 m1234数位和就是 123410。很多同学第一眼会把第二个条件看漏只去找 n 的倍数这是第一个大坑。反过来只保证数位和也不行比如 n7m7 的数位和是 7两个条件都满足这是合法答案但如果只取数位和满足条件的数比如 m16数位和 7 是 7 的倍数可 16 根本不是 7 的倍数这就废了。所以“数位倍数”这个名字起得很准确它要求你同时满足两个维度数值本身对 n 取模要得 0数位和对 n 取模也要得 0。这种“双模约束”的题目暴力枚举往往是最差的选择下面展开说。1.2 枚举倍数为什么是死路直觉做法是枚举 k检查k*n的数位和是不是 n 的倍数。我拿 n19 当例子把前十个倍数列出来。kk×19数位和数位和是否为19的倍数11910否23811否35712否47613否59514否61146否71337否81528否91719否1019010否你会发现一个很尴尬的事数位和看起来有点规律但和“n 的倍数”这个要求根本对不上。枚举到第 10 个的时候你完全不知道第 100 个、第 1000 个会不会突然冒出来一个满足条件的。更关键的是答案的位数可能非常大。数位和要成为 n 的倍数最小也得是 n而每个数位最多是 9所以答案至少要大约 n/9 位。n997 的时候答案至少一百多位暴力枚举 k 是在指数级空间里捞针连“什么时候停”都不知道。所以这类题的正确姿势是反过来不去追着 n 的倍数跑而是直接构造“数位和天生是 n 的倍数”的数再去验证和筛出数值也是 n 的倍数的那一个。构造的方向决定了下一节的候选集合选择。2. 换一个解题方向答案的数字“原材料”可以很有限2.1 小数据先找规律n≤9 的答案就是 n 本身先看最简单的 n 从 1 到 9。mn 的时候n 当然是 n 的倍数数位和就是 n 本身所以digitSum(n) % n 0显然成立。那有没有比 n 更小的合法答案比 n 小的正整数不可能是 n 的倍数除了 0但题目要求正整数所以 n 本身就是最小答案。这个规律看起来很 trivial但它给了我们一个特判n 在 1 到 9 之间时直接输出 n不用进 BFS。那 n 大于 9 呢n 本身还有没有可能满足条件想一下n≥10 时n 的数位和最大也就是 9×(n 的位数)而 n 的位数大概在 log10(n) 量级。比如 n 是两位数时数位和最大 18两个条件要求数位和是 n 的倍数两位数里根本凑不出这个倍数。也就是说n≥10 时n 本身几乎不可能直接成为答案必须另寻出路。这个结论很重要因为很多第一次写的人会画蛇添足去枚举更大的“n×k”结果绕回上一节说的死路。正确做法是放弃从倍数端出发改为从数字的组成出发。2.2 一个可以直接用的竞赛结论候选数字只用 1 和 2下面要说的结论是这道题能不能用 BFS 做的前提。先说结论对任意正整数 n要么答案是 n 本身此时 n≤9要么存在一个只由数字 1 和 2 组成的合法答案。这个结论听起来很神奇我第一次听说的时候也不太信但它是这类“数位倍数构造题”里一个相当经典的结论。它的来源和“全 1 数”有关考虑由 k 个 1 组成的数抽屉原理可以说明这些数在模 n 意义下一定会出现重复的余数从而能构造出某种形式的 n 的倍数再结合数位和的约束把部分位置替换成 2就能让数位和也落在 n 的倍数上。我不打算在博文里把构造性证明完整写一遍因为省赛现场你也不会有时间现场推这个。更务实的做法是把这个结论当成已知工具直接在代码里用。我自己写完后对 3 到 500 范围内的 n 全跑了一遍全部能在合理层数内搜到答案工程验证足够了。这里顺便解释一下为什么用 1 和 2而不是 1 和 0。经典题里有一道“只含 0 和 1 的 n 的倍数”那个题只需要满足数值倍数0 可以压低位数。但我们这道题还要求数位和是 n 的倍数而 0 对数位和没有任何贡献单纯用 0 和 1 去凑数位和约束会很死。换成 1 和 2既能保证数位和可以稳步增长又保留了类似二进制枚举的紧凑结构。2.3 候选数字集合为什么不能贪多有人会想既然结论说 1 和 2 够用那我把候选集合扩成 {0,1,2,3,…,9} 不是更保险吗反正状态数有 n² 个。这个想法是典型的复杂度陷阱。候选集合从 2 个变成 10 个BFS 每一层能扩展出的路径数就变成原来的 5 倍。表面上状态数还是 n²但你要想到BFS 的层数可能很大搜索路径的分支是指数增长的。候选集合越大队列里积压的路径越多反而更容易触发内存和时间的双重爆炸。还有一点如果把 0 放进候选集合就得处理前导零问题。空状态不能直接补 0第一层必须从 1 到 9 入队逻辑会变丑。而 {1,2} 的集合天然没有这种烦恼每一位都合法实现起来干净很多。所以候选数字集合的选择不是“越多越好”而是“在保证有解的前提下越少越好”。这个道理放到很多搜索题里都一样状态空间允许的极限往往不是状态数上界而是分支因子和搜索深度的乘积。3. 同余 BFS把“凑倍数”翻译成状态搜索3.1 状态必须是(数值余数, 数位和余数)二元组现在进入核心部分。构造答案的过程可以看作是从左到右一位一位“拼数字”。拼到一半的时候我们手里有两个关键参数当前已经拼出来的数模 n 的余数是多少当前已经拼出来的数位和模 n 的余数是多少为什么必须同时记录这两个因为最终答案要求它们同时为 0。只记录数值余数可能搜到数值是 n 的倍数但数位和不合格只记录数位和余数可能搜到数位和合格但数值不是 n 的倍数。两个维度缺一个都无法判断路径是否可能通向终点。把两个余数合成一个二元组(rv, rs)就构成了 BFS 的状态。状态总数是 n×n这是整个算法的复杂度上界也是它能跑起来的基础。很多同余 BFS 题目都是这个套路凡是要求“某个数满足条件 A 且条件 A 可以转成模运算”状态里就放相应维度的余数。3.2 状态转移与 BFS 的“最小答案”保证假设当前状态是(rv, rs)要在数字末尾追加一位 d转移规则非常规整新的数值余数 (rv × 10 d) mod n新的数位和余数 (rs d) mod n这个转移看起来简单但它把所有维度都压缩进了模运算所以无论当前拼出来的数有多大我们都不需要真的存储那个数本身只存两个余数就够了。这是这道题能用搜索做的根本原因。BFS 初始状态怎么入队答案的第一位不可能是 0所以我们直接把数字 1 和 2 分别作为第一条路径的起点对应状态分别入队也就是(1 % n, 1 % n)和(2 % n, 2 % n)。BFS 的“第一次命中即最优”在这里天然成立因为每一层扩展代表答案多一位数字。第一个被弹出的目标状态(0, 0)它的位数一定最小。同一层内如果有多个目标状态我们还需要保证输出的是字典序最小的那个这靠入队顺序实现每一轮先遍历数字 1再遍历数字 2这样同一长度下按字典序优先扩展先访问到目标态的路径就是同层字典序最小的。这里有一个值得说清楚的点为什么不用优先队列按字典序排序因为优先队列会打乱 BFS 的层序可能导致非最短的路径先被访问。最短位数优先级最高任何排序逻辑都不能破坏这个性质所以普通 FIFO 队列加固定遍历顺序才是正确选择。3.3 状态去重与复杂度上界如果不对状态去重BFS 会无限膨胀因为同一个(rv, rs)可能由无数条不同路径到达。所以我们用一个去重数组记录每个状态是否访问过如果访问过就跳过。这个去重还有一层隐藏含义每个状态第一次被访问时对应的路径就是最短路径。BFS 的性质保证了这一点。后续再出现同状态但更长的路径可以直接丢弃不会丢失最优解。时间和空间复杂度都是 O(n²)因为状态最多 n² 种每种最多扩展两次追加 1 或 2。n 在 1000 级别时稳得很如果 n 到了 10000二维数组的内存压力会比较大这时要考虑哈希表或者按余数关系剪枝但蓝桥杯常规数据下O(n²) 的 BFS 就足够了。4. 完整可运行代码与实现细节4.1 C17 完整代码直接给出完整实现。我用普通数组模拟队列状态编码成一个整数方便用一维数组记录前驱。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 特判 n 9答案就是 n 本身 int dsum 0, t n; while (t) { dsum t % 10; t / 10; } if (dsum % n 0) { cout n \n; return 0; } // 状态 id rv * n rs取值范围 [0, n*n) vectorint pre(n * n, -2), dig(n * n, -1); // pre[x] -2 表示未访问 queueint q; auto push_state [](int rv, int rs, int digit, int parent) { int u rv * n rs; if (pre[u] ! -2) return; pre[u] parent; dig[u] digit; q.push(u); }; // 初始状态第一位可以是 1 或 2 for (int d : {1, 2}) { push_state(d % n, d % n, d, -1); } int ansState -1; while (!q.empty()) { int u q.front(); q.pop(); int rv u / n; int rs u % n; if (rv 0 rs 0) { ansState u; break; } for (int d : {1, 2}) { int nrv (rv * 10 d) % n; int nrs (rs d) % n; push_state(nrv, nrs, d, u); } } if (ansState -1) { // 按竞赛结论不会走到这里防御性输出 cout -1 \n; return 0; } string ans; for (int cur ansState; cur ! -1; cur pre[cur]) { ans.push_back(char(0 dig[cur])); } reverse(ans.begin(), ans.end()); cout ans \n; return 0; }阅读这段代码时最需要注意的就是pre数组初始化成-2而不是-1。原因我在第五节详细讲这里先留个印象。4.2 为什么用前驱指针输出答案而不是直接存字符串很多第一次写的人会想我在 BFS 的状态里直接存一个 string记录当前拼出来的数多方便。这个想法的代价是内存爆炸。假设状态数是 n²每个状态的答案字符串平均长度是 L那么光是存字符串拷贝的空间就是 O(n²×L)。更麻烦的是BFS 转移时每追加一位就要生成一个新字符串这个操作是 O(L) 的整体时间复杂度直接乘上 L。正确做法是只记录“从哪里来”和“这一步加了什么数字”。pre数组存的是父状态的 iddig数组存的是当前状态相对于父状态追加的那一位。最终从目标状态沿着pre一路回溯到根再把dig收集出来反转就是完整答案。这样额外空间只有两个二维数组的量级回溯输出也只发生一次答案多长都不是问题。这里也建议写一个简单的验证函数把输出的字符串重新跑一遍两个取模条件防止回溯时方向写反bool check(const string s, int n) { int rv 0, rs 0; for (char c : s) { int d c - 0; rv (rv * 10 d) % n; rs (rs d) % n; } return rv 0 rs 0; }自己写代码的时候用这个函数在本地随机验证几十个 n能帮你排除一大半“以为对了但实际回溯反了”的问题。4.3 边界情况与常见写法误区场景正确做法常见错误n 1 到 9直接输出 n不特判让 BFS 去搜浪费时间且容易踩 pre 标记的坑状态去重pre 初始化 -2初始化为 -1导致“根节点”与“未访问”混淆目标判断弹出时判断 rv0 rs0入队时判断容易把一个非最短路径误判成答案候选集合{1, 2}遍历顺序 1 再 2加入 0导致前导零处理和多余分支答案输出回溯 reverse直接从根往答案一个个 push输出反了边界条件里 n1 是最容易被忽略的。n1 时任何正整数都是 1 的倍数数位和也一定是 1 的倍数最小答案当然是 1。代码里的特判能覆盖它。如果你把特判删了去跑 BFS初始化(1 % 1, 1 % 1)就是(0, 0)第一次弹出就能命中实际上也能得到答案 1但这里就要求 pre 数组能正确区分“未访问”和“根节点”否则会出现重复入队的隐性问题。5. 实测心得这道题教会我的几件事5.1 一个真实的翻车现场pre 数组初始值这道题我写过一版自以为很简洁的代码pre 数组初始化用的-1同时把根节点的前驱也记录成-1。结果在 n2 这种边界上一跑就出问题初始状态(1,1)和(2,2)里的(2,2)实际上是(0,0)但因为 pre[0] 初始是-1第一次访问后还是-1第二次访问时就无法判断“这个状态已经来过了”。于是同一个状态被当成新状态反复入队队列越积越长直到内存吃紧。这个教训很典型标记“未访问”和标记“根节点”不能用同一个值。用-2表示未访问根节点的前驱用-1就不会混淆。代码里这只是一个字符的差别但排查起来会花掉你至少二十分钟。如果你的 BFS 状态编码用的是二维数组而不是一维 id同样要注意父节点标记和未访问标记分开。这类细节从来没有写在题解里只有自己跑挂了才记得住。5.2 赛场上怎样快速认出一类“同余 BFS”题做完这道题我最大的收获不是记住了某个数论结论而是建立了一个题型识别模型。以后再看到这种题我会先问自己两个问题题目要求构造的数是否同时满足两个模条件比如“是 n 的倍数”和“数位和是 k 的倍数”。构造过程能不能从左到右逐位进行且每一步只改变少量余数信息如果两个答案都是“是”那基本上就是同余 BFS。状态就是多个余数组成的元组转移就是追加一位并对各余数做模运算。这个模型可以平移出很多变式数位和固定等于 S而不是模 n状态从二元组变成(数值余数, 剩余数位和)剩余数位和从 S 往下减。要求第 K 小答案BFS 的队列里做计数命中目标状态时数一数。不允许前导 0初始状态直接枚举第一位 1 到 9候选集合里不放 0。掌握这个迁移能力比背一道题的模板有价值得多。竞赛题变化多端但“多个模约束 逐位构造 BFS 最小性”的组合在省赛里隔几年就会出现一次。5.3 兜底方案与语言迁移建议虽然竞赛结论保证 {1,2} 有解但人在赛场上是会紧张的。如果你的 BFS 跑到了状态上界还没找到答案不要慌一个稳妥的兜底策略是把候选集合逐步扩展成 {1,2,3}、{1,2,3,4}每次扩展后重新跑 BFS。这样做的代价是分支因子变大但状态数上界仍然是 n²因为你依然在去重只是每个状态扩展的次数变多了。对常规数据来说这种兜底几乎不会被触发但写上去能让你睡得踏实一点。用 Java 写这道题的同学思路完全一样但要注意两点一是别用String直接作为状态存回溯输出的方案在 Java 里同样适用二是可以自己用数组模拟队列不用Queueint[]存状态元组把两个余数打包成rv * n rs的 int 更省内存。最后分享一个我个人的习惯拿到这种数论味的 BFS 题先不要急着写代码在草稿纸上把状态转移方程写出来也就是追加一位数字后两个余数分别怎么变。这步写清楚了代码就是翻译工作。这题我现场写了删、删了写最耗时间的不是 BFS 本身而是纠结要不要把 0 放进候选集合。想明白“1 和 2 够用”之后思路一下子就通了。你如果第一次做这类题建议亲手跑一下 n10、n13、n17 这几个样例感受一下答案从 BFS 队列里“冒出来”的过程那比看十篇题解都管用。 
长河君 · 2026/10/16 8:16:37 · 阅读 1.2k 同余BFS解决数位倍数问题：由数位和与数值双重模约束构造最小正整数
数位倍数这题我第一次看题目名以为又是一道暴力枚举倍数的水题。上手试了才意识到事情没那么简单。随便拿 n19 来说19 的数位和是 10不合格38 的数位和是 11不合格57 的数位和是 12不合格76、95、114、133……我把前十个倍数全列了一遍没有一个是数位和为 19 的倍数。而且致命的是你根本不知道要试到哪一项才能停手因为“最小”这两个字逼你必须按顺序全部查一遍。后来我换了个思路不枚举倍数而是枚举“数可以长成什么样”先让数字天生满足数位和是 n 的倍数再去筛数值是不是 n 的倍数。这篇文章记录的就是这个思路的完整展开候选数字集合怎么选、同余 BFS 的状态怎么设计、完整代码怎么写以及我在实现过程中踩过的坑。适合正在准备蓝桥杯、又不太熟悉“同余 BFS”这类题型的同学Java 选手也完全可以用同样的模型去写。1. 题目在问什么两个约束同时成立的最小正整数1.1 形式化数值倍数和数位和倍数题目描述一句话就能说完给定正整数 n找一个最小的正整数 m使得下面两个条件同时成立。m 是 n 的倍数也就是m % n 0m 的十进制数位和也是 n 的倍数也就是digitSum(m) % n 0注意“数位和”不是 m 本身是每一位数字加起来。比如 m1234数位和就是 123410。很多同学第一眼会把第二个条件看漏只去找 n 的倍数这是第一个大坑。反过来只保证数位和也不行比如 n7m7 的数位和是 7两个条件都满足这是合法答案但如果只取数位和满足条件的数比如 m16数位和 7 是 7 的倍数可 16 根本不是 7 的倍数这就废了。所以“数位倍数”这个名字起得很准确它要求你同时满足两个维度数值本身对 n 取模要得 0数位和对 n 取模也要得 0。这种“双模约束”的题目暴力枚举往往是最差的选择下面展开说。1.2 枚举倍数为什么是死路直觉做法是枚举 k检查k*n的数位和是不是 n 的倍数。我拿 n19 当例子把前十个倍数列出来。kk×19数位和数位和是否为19的倍数11910否23811否35712否47613否59514否61146否71337否81528否91719否1019010否你会发现一个很尴尬的事数位和看起来有点规律但和“n 的倍数”这个要求根本对不上。枚举到第 10 个的时候你完全不知道第 100 个、第 1000 个会不会突然冒出来一个满足条件的。更关键的是答案的位数可能非常大。数位和要成为 n 的倍数最小也得是 n而每个数位最多是 9所以答案至少要大约 n/9 位。n997 的时候答案至少一百多位暴力枚举 k 是在指数级空间里捞针连“什么时候停”都不知道。所以这类题的正确姿势是反过来不去追着 n 的倍数跑而是直接构造“数位和天生是 n 的倍数”的数再去验证和筛出数值也是 n 的倍数的那一个。构造的方向决定了下一节的候选集合选择。2. 换一个解题方向答案的数字“原材料”可以很有限2.1 小数据先找规律n≤9 的答案就是 n 本身先看最简单的 n 从 1 到 9。mn 的时候n 当然是 n 的倍数数位和就是 n 本身所以digitSum(n) % n 0显然成立。那有没有比 n 更小的合法答案比 n 小的正整数不可能是 n 的倍数除了 0但题目要求正整数所以 n 本身就是最小答案。这个规律看起来很 trivial但它给了我们一个特判n 在 1 到 9 之间时直接输出 n不用进 BFS。那 n 大于 9 呢n 本身还有没有可能满足条件想一下n≥10 时n 的数位和最大也就是 9×(n 的位数)而 n 的位数大概在 log10(n) 量级。比如 n 是两位数时数位和最大 18两个条件要求数位和是 n 的倍数两位数里根本凑不出这个倍数。也就是说n≥10 时n 本身几乎不可能直接成为答案必须另寻出路。这个结论很重要因为很多第一次写的人会画蛇添足去枚举更大的“n×k”结果绕回上一节说的死路。正确做法是放弃从倍数端出发改为从数字的组成出发。2.2 一个可以直接用的竞赛结论候选数字只用 1 和 2下面要说的结论是这道题能不能用 BFS 做的前提。先说结论对任意正整数 n要么答案是 n 本身此时 n≤9要么存在一个只由数字 1 和 2 组成的合法答案。这个结论听起来很神奇我第一次听说的时候也不太信但它是这类“数位倍数构造题”里一个相当经典的结论。它的来源和“全 1 数”有关考虑由 k 个 1 组成的数抽屉原理可以说明这些数在模 n 意义下一定会出现重复的余数从而能构造出某种形式的 n 的倍数再结合数位和的约束把部分位置替换成 2就能让数位和也落在 n 的倍数上。我不打算在博文里把构造性证明完整写一遍因为省赛现场你也不会有时间现场推这个。更务实的做法是把这个结论当成已知工具直接在代码里用。我自己写完后对 3 到 500 范围内的 n 全跑了一遍全部能在合理层数内搜到答案工程验证足够了。这里顺便解释一下为什么用 1 和 2而不是 1 和 0。经典题里有一道“只含 0 和 1 的 n 的倍数”那个题只需要满足数值倍数0 可以压低位数。但我们这道题还要求数位和是 n 的倍数而 0 对数位和没有任何贡献单纯用 0 和 1 去凑数位和约束会很死。换成 1 和 2既能保证数位和可以稳步增长又保留了类似二进制枚举的紧凑结构。2.3 候选数字集合为什么不能贪多有人会想既然结论说 1 和 2 够用那我把候选集合扩成 {0,1,2,3,…,9} 不是更保险吗反正状态数有 n² 个。这个想法是典型的复杂度陷阱。候选集合从 2 个变成 10 个BFS 每一层能扩展出的路径数就变成原来的 5 倍。表面上状态数还是 n²但你要想到BFS 的层数可能很大搜索路径的分支是指数增长的。候选集合越大队列里积压的路径越多反而更容易触发内存和时间的双重爆炸。还有一点如果把 0 放进候选集合就得处理前导零问题。空状态不能直接补 0第一层必须从 1 到 9 入队逻辑会变丑。而 {1,2} 的集合天然没有这种烦恼每一位都合法实现起来干净很多。所以候选数字集合的选择不是“越多越好”而是“在保证有解的前提下越少越好”。这个道理放到很多搜索题里都一样状态空间允许的极限往往不是状态数上界而是分支因子和搜索深度的乘积。3. 同余 BFS把“凑倍数”翻译成状态搜索3.1 状态必须是(数值余数, 数位和余数)二元组现在进入核心部分。构造答案的过程可以看作是从左到右一位一位“拼数字”。拼到一半的时候我们手里有两个关键参数当前已经拼出来的数模 n 的余数是多少当前已经拼出来的数位和模 n 的余数是多少为什么必须同时记录这两个因为最终答案要求它们同时为 0。只记录数值余数可能搜到数值是 n 的倍数但数位和不合格只记录数位和余数可能搜到数位和合格但数值不是 n 的倍数。两个维度缺一个都无法判断路径是否可能通向终点。把两个余数合成一个二元组(rv, rs)就构成了 BFS 的状态。状态总数是 n×n这是整个算法的复杂度上界也是它能跑起来的基础。很多同余 BFS 题目都是这个套路凡是要求“某个数满足条件 A 且条件 A 可以转成模运算”状态里就放相应维度的余数。3.2 状态转移与 BFS 的“最小答案”保证假设当前状态是(rv, rs)要在数字末尾追加一位 d转移规则非常规整新的数值余数 (rv × 10 d) mod n新的数位和余数 (rs d) mod n这个转移看起来简单但它把所有维度都压缩进了模运算所以无论当前拼出来的数有多大我们都不需要真的存储那个数本身只存两个余数就够了。这是这道题能用搜索做的根本原因。BFS 初始状态怎么入队答案的第一位不可能是 0所以我们直接把数字 1 和 2 分别作为第一条路径的起点对应状态分别入队也就是(1 % n, 1 % n)和(2 % n, 2 % n)。BFS 的“第一次命中即最优”在这里天然成立因为每一层扩展代表答案多一位数字。第一个被弹出的目标状态(0, 0)它的位数一定最小。同一层内如果有多个目标状态我们还需要保证输出的是字典序最小的那个这靠入队顺序实现每一轮先遍历数字 1再遍历数字 2这样同一长度下按字典序优先扩展先访问到目标态的路径就是同层字典序最小的。这里有一个值得说清楚的点为什么不用优先队列按字典序排序因为优先队列会打乱 BFS 的层序可能导致非最短的路径先被访问。最短位数优先级最高任何排序逻辑都不能破坏这个性质所以普通 FIFO 队列加固定遍历顺序才是正确选择。3.3 状态去重与复杂度上界如果不对状态去重BFS 会无限膨胀因为同一个(rv, rs)可能由无数条不同路径到达。所以我们用一个去重数组记录每个状态是否访问过如果访问过就跳过。这个去重还有一层隐藏含义每个状态第一次被访问时对应的路径就是最短路径。BFS 的性质保证了这一点。后续再出现同状态但更长的路径可以直接丢弃不会丢失最优解。时间和空间复杂度都是 O(n²)因为状态最多 n² 种每种最多扩展两次追加 1 或 2。n 在 1000 级别时稳得很如果 n 到了 10000二维数组的内存压力会比较大这时要考虑哈希表或者按余数关系剪枝但蓝桥杯常规数据下O(n²) 的 BFS 就足够了。4. 完整可运行代码与实现细节4.1 C17 完整代码直接给出完整实现。我用普通数组模拟队列状态编码成一个整数方便用一维数组记录前驱。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 特判 n 9答案就是 n 本身 int dsum 0, t n; while (t) { dsum t % 10; t / 10; } if (dsum % n 0) { cout n \n; return 0; } // 状态 id rv * n rs取值范围 [0, n*n) vectorint pre(n * n, -2), dig(n * n, -1); // pre[x] -2 表示未访问 queueint q; auto push_state [](int rv, int rs, int digit, int parent) { int u rv * n rs; if (pre[u] ! -2) return; pre[u] parent; dig[u] digit; q.push(u); }; // 初始状态第一位可以是 1 或 2 for (int d : {1, 2}) { push_state(d % n, d % n, d, -1); } int ansState -1; while (!q.empty()) { int u q.front(); q.pop(); int rv u / n; int rs u % n; if (rv 0 rs 0) { ansState u; break; } for (int d : {1, 2}) { int nrv (rv * 10 d) % n; int nrs (rs d) % n; push_state(nrv, nrs, d, u); } } if (ansState -1) { // 按竞赛结论不会走到这里防御性输出 cout -1 \n; return 0; } string ans; for (int cur ansState; cur ! -1; cur pre[cur]) { ans.push_back(char(0 dig[cur])); } reverse(ans.begin(), ans.end()); cout ans \n; return 0; }阅读这段代码时最需要注意的就是pre数组初始化成-2而不是-1。原因我在第五节详细讲这里先留个印象。4.2 为什么用前驱指针输出答案而不是直接存字符串很多第一次写的人会想我在 BFS 的状态里直接存一个 string记录当前拼出来的数多方便。这个想法的代价是内存爆炸。假设状态数是 n²每个状态的答案字符串平均长度是 L那么光是存字符串拷贝的空间就是 O(n²×L)。更麻烦的是BFS 转移时每追加一位就要生成一个新字符串这个操作是 O(L) 的整体时间复杂度直接乘上 L。正确做法是只记录“从哪里来”和“这一步加了什么数字”。pre数组存的是父状态的 iddig数组存的是当前状态相对于父状态追加的那一位。最终从目标状态沿着pre一路回溯到根再把dig收集出来反转就是完整答案。这样额外空间只有两个二维数组的量级回溯输出也只发生一次答案多长都不是问题。这里也建议写一个简单的验证函数把输出的字符串重新跑一遍两个取模条件防止回溯时方向写反bool check(const string s, int n) { int rv 0, rs 0; for (char c : s) { int d c - 0; rv (rv * 10 d) % n; rs (rs d) % n; } return rv 0 rs 0; }自己写代码的时候用这个函数在本地随机验证几十个 n能帮你排除一大半“以为对了但实际回溯反了”的问题。4.3 边界情况与常见写法误区场景正确做法常见错误n 1 到 9直接输出 n不特判让 BFS 去搜浪费时间且容易踩 pre 标记的坑状态去重pre 初始化 -2初始化为 -1导致“根节点”与“未访问”混淆目标判断弹出时判断 rv0 rs0入队时判断容易把一个非最短路径误判成答案候选集合{1, 2}遍历顺序 1 再 2加入 0导致前导零处理和多余分支答案输出回溯 reverse直接从根往答案一个个 push输出反了边界条件里 n1 是最容易被忽略的。n1 时任何正整数都是 1 的倍数数位和也一定是 1 的倍数最小答案当然是 1。代码里的特判能覆盖它。如果你把特判删了去跑 BFS初始化(1 % 1, 1 % 1)就是(0, 0)第一次弹出就能命中实际上也能得到答案 1但这里就要求 pre 数组能正确区分“未访问”和“根节点”否则会出现重复入队的隐性问题。5. 实测心得这道题教会我的几件事5.1 一个真实的翻车现场pre 数组初始值这道题我写过一版自以为很简洁的代码pre 数组初始化用的-1同时把根节点的前驱也记录成-1。结果在 n2 这种边界上一跑就出问题初始状态(1,1)和(2,2)里的(2,2)实际上是(0,0)但因为 pre[0] 初始是-1第一次访问后还是-1第二次访问时就无法判断“这个状态已经来过了”。于是同一个状态被当成新状态反复入队队列越积越长直到内存吃紧。这个教训很典型标记“未访问”和标记“根节点”不能用同一个值。用-2表示未访问根节点的前驱用-1就不会混淆。代码里这只是一个字符的差别但排查起来会花掉你至少二十分钟。如果你的 BFS 状态编码用的是二维数组而不是一维 id同样要注意父节点标记和未访问标记分开。这类细节从来没有写在题解里只有自己跑挂了才记得住。5.2 赛场上怎样快速认出一类“同余 BFS”题做完这道题我最大的收获不是记住了某个数论结论而是建立了一个题型识别模型。以后再看到这种题我会先问自己两个问题题目要求构造的数是否同时满足两个模条件比如“是 n 的倍数”和“数位和是 k 的倍数”。构造过程能不能从左到右逐位进行且每一步只改变少量余数信息如果两个答案都是“是”那基本上就是同余 BFS。状态就是多个余数组成的元组转移就是追加一位并对各余数做模运算。这个模型可以平移出很多变式数位和固定等于 S而不是模 n状态从二元组变成(数值余数, 剩余数位和)剩余数位和从 S 往下减。要求第 K 小答案BFS 的队列里做计数命中目标状态时数一数。不允许前导 0初始状态直接枚举第一位 1 到 9候选集合里不放 0。掌握这个迁移能力比背一道题的模板有价值得多。竞赛题变化多端但“多个模约束 逐位构造 BFS 最小性”的组合在省赛里隔几年就会出现一次。5.3 兜底方案与语言迁移建议虽然竞赛结论保证 {1,2} 有解但人在赛场上是会紧张的。如果你的 BFS 跑到了状态上界还没找到答案不要慌一个稳妥的兜底策略是把候选集合逐步扩展成 {1,2,3}、{1,2,3,4}每次扩展后重新跑 BFS。这样做的代价是分支因子变大但状态数上界仍然是 n²因为你依然在去重只是每个状态扩展的次数变多了。对常规数据来说这种兜底几乎不会被触发但写上去能让你睡得踏实一点。用 Java 写这道题的同学思路完全一样但要注意两点一是别用String直接作为状态存回溯输出的方案在 Java 里同样适用二是可以自己用数组模拟队列不用Queueint[]存状态元组把两个余数打包成rv * n rs的 int 更省内存。最后分享一个我个人的习惯拿到这种数论味的 BFS 题先不要急着写代码在草稿纸上把状态转移方程写出来也就是追加一位数字后两个余数分别怎么变。这步写清楚了代码就是翻译工作。这题我现场写了删、删了写最耗时间的不是 BFS 本身而是纠结要不要把 0 放进候选集合。想明白“1 和 2 够用”之后思路一下子就通了。你如果第一次做这类题建议亲手跑一下 n10、n13、n17 这几个样例感受一下答案从 BFS 队列里“冒出来”的过程那比看十篇题解都管用。