先说个我上周在群里看到的题目给你一个数n只允许“简单修改一个 n”也就是改掉十进制表示里的某一位数字让它变成 7 的倍数。有人第一反应是“直接对 7 取模判断不就行了”可真写起来才发现坑不少。这篇文章就把这个题从数学原理到代码实操完整拆开顺便把我在本地测试时踩过的几个边界情况一起讲清楚适合正在刷算法题、或者想巩固大整数取模思路的朋友参考。1. 先把题看懂修改的是哪一位、变成谁的倍数1.1 “简单修改一个 n”的三种常见理解这类题目在算法群里经常出现但题面往往写得特别随意导致每个人理解都不一样。我至少见过三种解读第一种改十进制表示中的某一位数字。也就是把n12345这种字符串里的一位比如把2改成8得到18345再去判断它是不是 7 的倍数。这应该是标题里最自然的意思也是我下文要实现的主版本。第二种对数值本身做加减乘除。比如有人理解为“给 n 加上或减去一个很小的数”这其实就变成了枚举n1、n2、n-1这种。虽然也能做但“修改一个 n”这个说法就显得很怪而且题目如果只要求加减一位那直接枚举n±k就好跟“修改哪一位”没关系。第三种修改程序里的一个变量n。比如有人拿到的代码里有个n是死值改一下变成 7 的倍数。这种属于工程问题通常还要配合确认数据范围、输入来源不太像算法题的核心考点。我后面会默认采用第一种理解把n看成由数字字符组成的字符串只允许替换其中一位为0到9的某个数字要求替换后的整数能被 7 整除。如果你想问的是其他版本思路也能平移过去只是细节不同。1.2 解题的第一步先把“7 的倍数”翻译成余数判断一个数是不是 7 的倍数最朴素的办法就是直接算n % 7。这个思路本身没问题问题出在“大数”上。如果n只有int范围内的十几位那不管怎么改用long long都能直接算完。但一旦n是 100 位、1000 位甚至 100 万位的大整数任何内置整数类型都会溢出。这时候不能依赖语言自带的大整数库而是要用字符串配合模运算逐位处理。原理其实一句话十进制数abcdefg等于a * 10^6 b * 10^5 c * 10^4 d * 10^3 e * 10^2 f * 10 g两边同时取模 7就变成(a * 10^6 b * 10^5 c * 10^4 d * 10^3 e * 10^2 f * 10 g) mod 7由于乘法和加法都满足模运算的分配律我可以从最高位开始每读一位就做一次remainder (remainder * 10 digit) % 7扫完后得到的remainder就是整个大数对 7 的余数。这个操作只需要一次线性扫描时间复杂度 O(len)空间只要几个变量。所以第一步不是写千奇百怪的“7 整除判断规则”而是先把原数n的余数算出来。后面所有修改方案本质上都是在算“修改带来的增量”对这个余数的影响。1.3 整体思路从枚举到优化拿到余数后最直接的做法是枚举所有可能修改的位置和所有可能的数字。假定n的长度为len每一位 i 从高位到低位编号比如最高位是第 0 位。对第 i 位做替换就是把原来的数字d_old换成d_new数值变化量为(d_new - d_old) * 10^(len-1-i)因此新的余数就是new_remainder (old_remainder (d_new - d_old) * 10^(len-1-i)) mod 7只要new_remainder 0这个方案就成立。枚举每一位的 0 到 9总共最多len * 10次检查哪怕字符串有十万位也只需要百万级运算非常快。这里有一个容易忽略的前提字符串可能非常长所以不能每一次都重新计算整个新数对 7 的余数而是要把10^(len-1-i) mod 7提前算好或者用循环节快速求出。后面我会专门讲这个数学工具。2. 数学工具为什么 7 的整除规则帮不上忙2.1 10 的幂次模 7 循环节很多小学生都背过“7 的整除判断法”比如末三位与高位差之类但那种规则在“只改一位”的场景下非常不好用。因为修改的位置可能出现在任意一位你需要知道这一位对应的权值10^k对 7 的余数。好在这里有个关键规律10^k mod 7的值是按周期循环的。我直接列一下10^0 mod 7 1 10^1 mod 7 3 10^2 mod 7 2 10^3 mod 7 6 10^4 mod 7 4 10^5 mod 7 5 10^6 mod 7 1可以看到从10^6开始又回到了 1所以循环节长度是 6。换句话说第 k 位的权值只跟k mod 6有关。这个循环节有什么用如果位数不多直接循环乘 10 取余也不会慢。但如果位数是百万级你总不可能为每一位重新算一次快速幂。有了循环节我可以在一次预处理中算好所有位置对 7 的权值或者干脆只保留 6 种状态后面遇到相同的位置直接取结果。生活化类比一下就像钟表表盘只有 12 个数字你看到 37 点就知道实际上是凌晨 1 点10 的幂次对 7 取余也一样每转 6 圈就回到原点。还需要注意一点循环节里的 6 个余数并不是 1 到 6 的递增排列而是1, 3, 2, 6, 4, 5。我一开始还以为是1, 3, 2, 6, 4, 5没错但有人会误算成1, 3, 2, 6, 4, 5是某个斐波那契数列的变形其实只是 10 的幂次取余的自然结果。算的时候老老实实手推一遍最稳。2.2 用“一位增量”方程描述修改假设原数是n余数是r n mod 7。如果想修改第 i 位把原来数字a变成b那么这一位的变化量是delta (b - a) * w_i其中w_i 10^(len-1-i) mod 7。修改后的余数就是new_r (r delta) mod 7要让new_r 0即(r (b - a) * w_i) mod 7 0整理一下就是(b - a) * w_i mod 7 (7 - r) mod 7因为b - a的范围是从 -9 到 9w_i只有 6 种取值所以这一步检查非常轻量。这里真正耗时的不是检查而是枚举。最直观的写法是枚举所有 i 和所有 b逐个判断。但在做之前可以先算一下“我还差多少余数才能到 0”need (7 - r) % 7接下来只需要看是否存在某个位置 i 和某个数字 b使得增量对 7 取余等于 need。这个视角可以把问题从“验证每个新数”变成“搜索合法增量”思路清爽很多。还要提醒一件事如果need 0意味着原数本身已经是 7 的倍数。如果题目允许“不修改”或不要求必须修改那n本身就是答案。但如果题目强制要求“必须修改一位”那就要继续找有没有别的方案这样就可能变成无解。2.3 边界与陷阱我实际写代码时被三个边界坑过。第一个是首位不能变成 0。如果n是12345把首位1改成0得到02345也就是 2345。虽然数值上没问题但题目只要说“十进制表示不变形”这种修改通常算非法因为会引入前导零。判断条件很简单i 0时b不能是 0。第二个是只有一个数字的情况。比如n 7它是 7 的倍数。如果允许不修改答案就是它如果强制修改那n没有任何别的数字可以换只能判无解。类似n 1判断1到9里哪个数能被 7 整除只有7可以所以答案就是 7。这些看起来简单的小例子恰恰能测出代码里首位的特殊处理是否写对。第三个是多解时如何选择输出。有人要的是“任意一组合法解”有人要的是“修改后的数最小”或“修改位置最靠左”。这两者的优先级不同如果要求修改后的数最大那你不能只找一个解就停而是要把所有候选都跑一遍按字符串或数值比较。这里建议先读清楚题目要求否则会做错方向。3. 动手实现一份可直接跑通的代码3.1 Python 版本先把功能跑通我直接用字符串处理不转大整数这样支持任意长度的n。下面这份代码核心逻辑很清晰适合当模板。def solve(n_str: str): # 1. 先计算原数对 7 的余数 r 0 for ch in n_str: r (r * 10 int(ch)) % 7 length len(n_str) # 2. 预处理每一位的权值 10^(len-1-i) mod 7 # 指数从最高位开始递减利用循环节可以直接算 weight [] # 计算 10^(length-1) mod 7 cur_pow pow(10, length - 1, 7) for i in range(length): weight.append(cur_pow) # 下一位是 /10等价于乘上 10 在模 7 下的逆元 # 由于 10 mod 7 3乘 3 后恰好等价于除以 10 的效果 # 更简单的方式需要重新推导见下方注释等一下我上面的注释有点误导。因为10在模 7 意义下其实不是简单乘法逆元不过我可以用更直接的方式先建一个长度为 6 的循环表然后根据指数length-1-i对 6 取余来取值。这样最清晰。def solve(n_str: str): # 1. 计算原数对 7 的余数 r 0 for ch in n_str: r (r * 10 int(ch)) % 7 length len(n_str) # 2. 10^k mod 7 的循环节 cycle [1, 3, 2, 6, 4, 5] # 10^k % 7, k0..5 # 3. 枚举修改第 i 位 # 第 i 位从0开始对应指数 len-1-i for i in range(length): old_digit int(n_str[i]) # 从高到低枚举新数字保证第一个找到的解尽量靠左且该位尽可能小 for new_digit in range(0, 10): if new_digit old_digit: continue # 首位不能变 0 if i 0 and new_digit 0: continue # 该位权值 exp length - 1 - i w cycle[exp % 6] delta (new_digit - old_digit) * w new_r (r delta) % 7 if new_r 0: # 生成结果字符串 ans n_str[:i] str(new_digit) n_str[i1:] return ans return -1 # 无解 if __name__ __main__: test_cases [1, 7, 70, 12345, 1000000000000000000000000] for t in test_cases: print(t, -, solve(t))这个实现有几个值得注意的细节cycle[exp % 6]保证了指数不管多大都能快速映射到正确的权值。枚举新数字时从 0 到 9。这里因为“优先选择靠左位置”所以外层循环按 i 从 0 到 length-1 枚举位置。如果你希望修改后数值最小那在同一个位置内应该优先换更小的数字如果你希望修改后数值最大则应该把内层循环改成从 9 到 0。返回-1代表无解。有些题目要求改为输出-1真实应用里记得先确认题目的无解约定。3.2 关键参数与复杂度分析这个算法时间复杂度是O(length * 10)也就是O(length)因为 10 是常数。空间复杂度是O(1)循环节数组固定大小不需要额外拷贝字符串。一般来讲如果n的长度是几万这个解法跑起来都是毫秒级。更极端一点如果长度是一百万也只要一千多万次内层循环Python 大约一两秒内能完成。这比“每改一位就重新生成字符串并整串取模”的 O(length^2) 快得多。我见过有人一开始写成每次修改后调用int(new_str) % 7然后n一旦超过 100 位就疯狂报错或者直接跑死。原因有两个一是大整数转换非常昂贵二是每次都要把整个字符串扫一遍。所以提前算好原数余数和权重的思路不是锦上添花而是这种东西能够跑起来的核心原因。再举个例子说明复杂度差异假设 length 10000朴素的“每次改完后解析成 int”大约要做 10 万次大数运算每次大数运算又和长度相关总体可能是千万级别而线性扫描方案只需要 10 万次轻量整数运算速度可能差几十倍。3.3 C 和 Java 实现时的注意点Python 里我直接用字符串切片拼接很方便。但如果用 C 或 Java有几点建议C 中不要贪图方便用std::stoll去转换字符串因为stoll只支持有限长度。正确做法是维护一个string修改字符后用循环取模验证或者更高效地复用预先算好的原数余数。C 的std::string修改某一位非常便宜s[i] 0 new_digit即可。另外如果你要在循环里不断生成新串注意std::string的拷贝成本尽量直接替换再还原。Java 中要用long也不要存整个大数。其实只算余数时用int就够了因为任何中间值乘 10 加个位数后对 7 取模结果范围始终在 0 到 6不会溢出。真正需要小心的是char转数字时记得减去0否则会把 ASCII 码当成数字算进去。还要统一一下循环节的计算方式。如果你不想写死循环表可以直接在代码里动态生成cycle [] x 1 for k in range(6): cycle.append(x) x (x * 10) % 7这样即使以后换成判断 3、11、13 之类的数也只需要改动模数代码复用性更高。4. 常见问题与排查技巧实录4.1 原数本身就是 7 的倍数怎么办这是最容易被出题人挖坑的点。如果题面写的是“找到某个修改方案使结果成为 7 的倍数”没有强调必须修改那原数本身就能算一个解。但很多题目为了提升难度会在题目描述里写“你必须正好修改一位”这时候如果n70原数是 7 的倍数你不能直接返回 70否则错误。需要继续找看是否存在某一位替换成别的数字后仍然是 7 的倍数。举个例子n 70 r 0 need 0把十位7改成0违法前导零改成其他数字比如1得到1010 mod 7 3不可行。把个位0改成1得到7171 mod 7 1不可行改成7得到7777 mod 7 0可行。所以如果强制修改答案是77。如果所有可能的修改都不能让余数为 0才返回无解。我建议函数设计上留一个must_change参数默认False这样同一个代码可以应付两种题目要求。4.2 首位变成 0 到底算不算合法这个问题没有统一答案。在某些程序设计竞赛里数字字符串转换后前导零通常被自动忽略所以0123等同于123。但在另一些题意里要求“得到一个新的整数”那前导零虽然不影响整数值却会让输出格式变成0123不少评测系统会直接判错。稳妥的做法是如果题目没明确说允许前导零一律禁止首位替换成 0。如果明确说“输出可以是带有前导零的字符串”那就放开限制。我写了一个开关变量方便切换allow_leading_zero False在枚举时这样判断if i 0 and new_digit 0 and not allow_leading_zero: continue这样既能满足大多数题目的要求也能在特殊题目下快速调整。4.3 多解情况下怎么按“字典序最小”输出我遇到过一个变体题要求“输出所有方案中字典序最小的那个”或者“修改后数字最小”。这种多解问题的优先级需要分两层看第一层是修改位置第二层是数字大小。对于“数字最小”的目标修改位置的优先级其实要结合长度来看。因为等长字符串比较字典序就是从左到右逐位比较所以越靠左的位置越关键。换句话说你要先找一个最靠左的、可行修改位置中能让该位数最小的方案。我上面的代码采用“位置从前往后、数字从小到大”的枚举顺序第一个满足条件的解正好就是字典序最小的解。如果你要的是“修改后数字最大”只需把内层循环的数字顺序反转并且保持外层位置从前往后。因为相同长度下最高位越大整个数越大。这里容易犯的错误是有人先找所有可行解然后用int排序。一旦字符串很长转int又溢出了。正确做法是保持字符串比较。4.4 测试用例设计速查表我在本地跑测试时会固定用下面这一组用例防止自己漏掉边界。输入 n说明期望输出must_changeFalse1单数字非倍数77单数字且本身就是倍数7不改时/ 无解若强制改70原数是倍数且还有合法修改77若强制改/ 70不改时10首位为1个位为01412345普通测试比如 12348 或 12341取决于枚举顺序999999999999稳定大数自行计算重点验证不溢出777777777777大数本身 7 的倍数根据 must_change 判断我建议你把第一个用例1实测一下程序应返回 7因为7 - 1 6而这一位恰好是权值 1所以直接改个位即可。第二个用例7如果不允许不改代码会遍历完所有可能性后返回-1这一步能验证must_change分支是否正确。4.5 一个我曾经犯过的低级错误最让我印象深刻的错误是权值计算方向写反了。我一开始把第 i 位的权值算成了10^i mod 7而不是10^(len-1-i) mod 7。结果对于回文类数字刚好碰巧能过但换个普通数字就出错。调试了很久才发现字符串最高位对应的是最高次幂不是最低次幂。这个问题可以用一个非常小的例子验证n 21它本身能被 7 整除但如果我们把十位从2改成1得到11不是倍数把个位从1改成2得到22也不是倍数。所以21在“必须修改”的前提下无解。当我权值方向写反时代码会误以为某些修改可行。所以我建议写完后一定打印几个手算用例别只靠随机大数测试。5. 扩展思考如果要求“修改两个数”或者“求最少修改次数”5.1 从“改一位”到“改两位”的递推很多题目就是一个引子改一位做完后紧接着会让你做“允许修改两位”的版本。如果只改一位状态空间是len * 10。改两位直接枚举两重位置和两重数字会复杂到O(len^2 * 100)在长度大了之后跑不动。这时候可以用动态规划。比较通用的一种做法是“自动机 余数状态”用dp[i][j][k]表示处理到第 i 位时已经修改了 j 位当前整个数字前缀对 7 的余数为 k 时是否可行。转移时有两种选择不修改第 i 位直接沿用原数字余数变成(k * 10 old_digit) % 7修改第 i 位为新数字d则修改次数加 1余数变成(k * 10 d) % 7。最后只要看dp[len][m][0]是否为真就能知道是否可行同时记录路径输出方案。这个思路把“修改次数”限制在最多 2 次或 m 次复杂度是O(len * m * 7 * 10)对于 m 很小的情况非常高效。如果 m 很大那又是另一个背包问题了。5.2 如果要输出“所有可行解”怎么办有些场景不是找任意解而是想把所有可行修改都输出。简单做法就是把命中条件从return改成列表收集。但要注意最多可能有len * 9个合法结果首位最多 9 个数字其他位最多 10 个数字但要去掉原数字在len很大时输出本身就会爆量。通常面试或竞赛中不会要求输出全部解而只会要求输出字典序最小或最大的那个。因此代码里准备好一个“解比较函数”比把所有解都存下来更稳。你可以边枚举边保留当前最优解最后统一输出。5.3 扩展到“模数不是 7”时循环节会怎样这个题最漂亮的地方在于“7”看似随机实际上是精心选过的。如果你把模数换成 8、9 或者 11循环节长度也会跟着变。比如模 8 时10^k mod 8从 k0 开始是1, 2, 4, 0, 0, 0...但到后面全是 0这会让高位修改完全不影响余数。也就是说判断 8 的倍数时其实只需要看末三位修改高位根本没意义。模 11 时循环节是1, 10, 1, 10...也就是奇数位和偶数位分别起作用。所以判断 11 的倍数可以简化为“奇数位和与偶数位和的差”。如果你只想做一道题的解法直接用 7 的循环节即可。但如果你想真正理解这题的套路我建议把模数参数化写成函数solve_mod(n_str, mod)内部动态生成循环节。以后遇到判断 7 的倍数变体一行代码就能复用。我的实操心得这个题表面上是“简单修改一个 n”实际上考察的是大整数取模和权重思想。很多人第一眼觉得“这不就是枚举吗”但不写出完整代码很难发现首位限制、必须修改、多解优先级这些隐藏条件。我自己在写完后用随机大数和暴力法对拍过几百组数据确认循环节方向没错。这里也建议你写完代码后用random.randint生成一些十几位的数跑一版“直接转 int 暴力枚举”的代码做对比两边答案一致再收工。最后再分享一个小技巧如果你在面试里遇到这种题可以先问清楚三个问题。第一能否不修改就输出原数第二修改后能否有前导零第三多解时优先靠左还是靠右。把这三个问题问完不仅代码不会写歪面试官也会觉得你考虑周全。这道题本身不难但能把边界一次说清的人往往才是真把这个知识点吃透了。
大整数取模：只改一位让数字成为7的倍数
先说个我上周在群里看到的题目给你一个数n只允许“简单修改一个 n”也就是改掉十进制表示里的某一位数字让它变成 7 的倍数。有人第一反应是“直接对 7 取模判断不就行了”可真写起来才发现坑不少。这篇文章就把这个题从数学原理到代码实操完整拆开顺便把我在本地测试时踩过的几个边界情况一起讲清楚适合正在刷算法题、或者想巩固大整数取模思路的朋友参考。1. 先把题看懂修改的是哪一位、变成谁的倍数1.1 “简单修改一个 n”的三种常见理解这类题目在算法群里经常出现但题面往往写得特别随意导致每个人理解都不一样。我至少见过三种解读第一种改十进制表示中的某一位数字。也就是把n12345这种字符串里的一位比如把2改成8得到18345再去判断它是不是 7 的倍数。这应该是标题里最自然的意思也是我下文要实现的主版本。第二种对数值本身做加减乘除。比如有人理解为“给 n 加上或减去一个很小的数”这其实就变成了枚举n1、n2、n-1这种。虽然也能做但“修改一个 n”这个说法就显得很怪而且题目如果只要求加减一位那直接枚举n±k就好跟“修改哪一位”没关系。第三种修改程序里的一个变量n。比如有人拿到的代码里有个n是死值改一下变成 7 的倍数。这种属于工程问题通常还要配合确认数据范围、输入来源不太像算法题的核心考点。我后面会默认采用第一种理解把n看成由数字字符组成的字符串只允许替换其中一位为0到9的某个数字要求替换后的整数能被 7 整除。如果你想问的是其他版本思路也能平移过去只是细节不同。1.2 解题的第一步先把“7 的倍数”翻译成余数判断一个数是不是 7 的倍数最朴素的办法就是直接算n % 7。这个思路本身没问题问题出在“大数”上。如果n只有int范围内的十几位那不管怎么改用long long都能直接算完。但一旦n是 100 位、1000 位甚至 100 万位的大整数任何内置整数类型都会溢出。这时候不能依赖语言自带的大整数库而是要用字符串配合模运算逐位处理。原理其实一句话十进制数abcdefg等于a * 10^6 b * 10^5 c * 10^4 d * 10^3 e * 10^2 f * 10 g两边同时取模 7就变成(a * 10^6 b * 10^5 c * 10^4 d * 10^3 e * 10^2 f * 10 g) mod 7由于乘法和加法都满足模运算的分配律我可以从最高位开始每读一位就做一次remainder (remainder * 10 digit) % 7扫完后得到的remainder就是整个大数对 7 的余数。这个操作只需要一次线性扫描时间复杂度 O(len)空间只要几个变量。所以第一步不是写千奇百怪的“7 整除判断规则”而是先把原数n的余数算出来。后面所有修改方案本质上都是在算“修改带来的增量”对这个余数的影响。1.3 整体思路从枚举到优化拿到余数后最直接的做法是枚举所有可能修改的位置和所有可能的数字。假定n的长度为len每一位 i 从高位到低位编号比如最高位是第 0 位。对第 i 位做替换就是把原来的数字d_old换成d_new数值变化量为(d_new - d_old) * 10^(len-1-i)因此新的余数就是new_remainder (old_remainder (d_new - d_old) * 10^(len-1-i)) mod 7只要new_remainder 0这个方案就成立。枚举每一位的 0 到 9总共最多len * 10次检查哪怕字符串有十万位也只需要百万级运算非常快。这里有一个容易忽略的前提字符串可能非常长所以不能每一次都重新计算整个新数对 7 的余数而是要把10^(len-1-i) mod 7提前算好或者用循环节快速求出。后面我会专门讲这个数学工具。2. 数学工具为什么 7 的整除规则帮不上忙2.1 10 的幂次模 7 循环节很多小学生都背过“7 的整除判断法”比如末三位与高位差之类但那种规则在“只改一位”的场景下非常不好用。因为修改的位置可能出现在任意一位你需要知道这一位对应的权值10^k对 7 的余数。好在这里有个关键规律10^k mod 7的值是按周期循环的。我直接列一下10^0 mod 7 1 10^1 mod 7 3 10^2 mod 7 2 10^3 mod 7 6 10^4 mod 7 4 10^5 mod 7 5 10^6 mod 7 1可以看到从10^6开始又回到了 1所以循环节长度是 6。换句话说第 k 位的权值只跟k mod 6有关。这个循环节有什么用如果位数不多直接循环乘 10 取余也不会慢。但如果位数是百万级你总不可能为每一位重新算一次快速幂。有了循环节我可以在一次预处理中算好所有位置对 7 的权值或者干脆只保留 6 种状态后面遇到相同的位置直接取结果。生活化类比一下就像钟表表盘只有 12 个数字你看到 37 点就知道实际上是凌晨 1 点10 的幂次对 7 取余也一样每转 6 圈就回到原点。还需要注意一点循环节里的 6 个余数并不是 1 到 6 的递增排列而是1, 3, 2, 6, 4, 5。我一开始还以为是1, 3, 2, 6, 4, 5没错但有人会误算成1, 3, 2, 6, 4, 5是某个斐波那契数列的变形其实只是 10 的幂次取余的自然结果。算的时候老老实实手推一遍最稳。2.2 用“一位增量”方程描述修改假设原数是n余数是r n mod 7。如果想修改第 i 位把原来数字a变成b那么这一位的变化量是delta (b - a) * w_i其中w_i 10^(len-1-i) mod 7。修改后的余数就是new_r (r delta) mod 7要让new_r 0即(r (b - a) * w_i) mod 7 0整理一下就是(b - a) * w_i mod 7 (7 - r) mod 7因为b - a的范围是从 -9 到 9w_i只有 6 种取值所以这一步检查非常轻量。这里真正耗时的不是检查而是枚举。最直观的写法是枚举所有 i 和所有 b逐个判断。但在做之前可以先算一下“我还差多少余数才能到 0”need (7 - r) % 7接下来只需要看是否存在某个位置 i 和某个数字 b使得增量对 7 取余等于 need。这个视角可以把问题从“验证每个新数”变成“搜索合法增量”思路清爽很多。还要提醒一件事如果need 0意味着原数本身已经是 7 的倍数。如果题目允许“不修改”或不要求必须修改那n本身就是答案。但如果题目强制要求“必须修改一位”那就要继续找有没有别的方案这样就可能变成无解。2.3 边界与陷阱我实际写代码时被三个边界坑过。第一个是首位不能变成 0。如果n是12345把首位1改成0得到02345也就是 2345。虽然数值上没问题但题目只要说“十进制表示不变形”这种修改通常算非法因为会引入前导零。判断条件很简单i 0时b不能是 0。第二个是只有一个数字的情况。比如n 7它是 7 的倍数。如果允许不修改答案就是它如果强制修改那n没有任何别的数字可以换只能判无解。类似n 1判断1到9里哪个数能被 7 整除只有7可以所以答案就是 7。这些看起来简单的小例子恰恰能测出代码里首位的特殊处理是否写对。第三个是多解时如何选择输出。有人要的是“任意一组合法解”有人要的是“修改后的数最小”或“修改位置最靠左”。这两者的优先级不同如果要求修改后的数最大那你不能只找一个解就停而是要把所有候选都跑一遍按字符串或数值比较。这里建议先读清楚题目要求否则会做错方向。3. 动手实现一份可直接跑通的代码3.1 Python 版本先把功能跑通我直接用字符串处理不转大整数这样支持任意长度的n。下面这份代码核心逻辑很清晰适合当模板。def solve(n_str: str): # 1. 先计算原数对 7 的余数 r 0 for ch in n_str: r (r * 10 int(ch)) % 7 length len(n_str) # 2. 预处理每一位的权值 10^(len-1-i) mod 7 # 指数从最高位开始递减利用循环节可以直接算 weight [] # 计算 10^(length-1) mod 7 cur_pow pow(10, length - 1, 7) for i in range(length): weight.append(cur_pow) # 下一位是 /10等价于乘上 10 在模 7 下的逆元 # 由于 10 mod 7 3乘 3 后恰好等价于除以 10 的效果 # 更简单的方式需要重新推导见下方注释等一下我上面的注释有点误导。因为10在模 7 意义下其实不是简单乘法逆元不过我可以用更直接的方式先建一个长度为 6 的循环表然后根据指数length-1-i对 6 取余来取值。这样最清晰。def solve(n_str: str): # 1. 计算原数对 7 的余数 r 0 for ch in n_str: r (r * 10 int(ch)) % 7 length len(n_str) # 2. 10^k mod 7 的循环节 cycle [1, 3, 2, 6, 4, 5] # 10^k % 7, k0..5 # 3. 枚举修改第 i 位 # 第 i 位从0开始对应指数 len-1-i for i in range(length): old_digit int(n_str[i]) # 从高到低枚举新数字保证第一个找到的解尽量靠左且该位尽可能小 for new_digit in range(0, 10): if new_digit old_digit: continue # 首位不能变 0 if i 0 and new_digit 0: continue # 该位权值 exp length - 1 - i w cycle[exp % 6] delta (new_digit - old_digit) * w new_r (r delta) % 7 if new_r 0: # 生成结果字符串 ans n_str[:i] str(new_digit) n_str[i1:] return ans return -1 # 无解 if __name__ __main__: test_cases [1, 7, 70, 12345, 1000000000000000000000000] for t in test_cases: print(t, -, solve(t))这个实现有几个值得注意的细节cycle[exp % 6]保证了指数不管多大都能快速映射到正确的权值。枚举新数字时从 0 到 9。这里因为“优先选择靠左位置”所以外层循环按 i 从 0 到 length-1 枚举位置。如果你希望修改后数值最小那在同一个位置内应该优先换更小的数字如果你希望修改后数值最大则应该把内层循环改成从 9 到 0。返回-1代表无解。有些题目要求改为输出-1真实应用里记得先确认题目的无解约定。3.2 关键参数与复杂度分析这个算法时间复杂度是O(length * 10)也就是O(length)因为 10 是常数。空间复杂度是O(1)循环节数组固定大小不需要额外拷贝字符串。一般来讲如果n的长度是几万这个解法跑起来都是毫秒级。更极端一点如果长度是一百万也只要一千多万次内层循环Python 大约一两秒内能完成。这比“每改一位就重新生成字符串并整串取模”的 O(length^2) 快得多。我见过有人一开始写成每次修改后调用int(new_str) % 7然后n一旦超过 100 位就疯狂报错或者直接跑死。原因有两个一是大整数转换非常昂贵二是每次都要把整个字符串扫一遍。所以提前算好原数余数和权重的思路不是锦上添花而是这种东西能够跑起来的核心原因。再举个例子说明复杂度差异假设 length 10000朴素的“每次改完后解析成 int”大约要做 10 万次大数运算每次大数运算又和长度相关总体可能是千万级别而线性扫描方案只需要 10 万次轻量整数运算速度可能差几十倍。3.3 C 和 Java 实现时的注意点Python 里我直接用字符串切片拼接很方便。但如果用 C 或 Java有几点建议C 中不要贪图方便用std::stoll去转换字符串因为stoll只支持有限长度。正确做法是维护一个string修改字符后用循环取模验证或者更高效地复用预先算好的原数余数。C 的std::string修改某一位非常便宜s[i] 0 new_digit即可。另外如果你要在循环里不断生成新串注意std::string的拷贝成本尽量直接替换再还原。Java 中要用long也不要存整个大数。其实只算余数时用int就够了因为任何中间值乘 10 加个位数后对 7 取模结果范围始终在 0 到 6不会溢出。真正需要小心的是char转数字时记得减去0否则会把 ASCII 码当成数字算进去。还要统一一下循环节的计算方式。如果你不想写死循环表可以直接在代码里动态生成cycle [] x 1 for k in range(6): cycle.append(x) x (x * 10) % 7这样即使以后换成判断 3、11、13 之类的数也只需要改动模数代码复用性更高。4. 常见问题与排查技巧实录4.1 原数本身就是 7 的倍数怎么办这是最容易被出题人挖坑的点。如果题面写的是“找到某个修改方案使结果成为 7 的倍数”没有强调必须修改那原数本身就能算一个解。但很多题目为了提升难度会在题目描述里写“你必须正好修改一位”这时候如果n70原数是 7 的倍数你不能直接返回 70否则错误。需要继续找看是否存在某一位替换成别的数字后仍然是 7 的倍数。举个例子n 70 r 0 need 0把十位7改成0违法前导零改成其他数字比如1得到1010 mod 7 3不可行。把个位0改成1得到7171 mod 7 1不可行改成7得到7777 mod 7 0可行。所以如果强制修改答案是77。如果所有可能的修改都不能让余数为 0才返回无解。我建议函数设计上留一个must_change参数默认False这样同一个代码可以应付两种题目要求。4.2 首位变成 0 到底算不算合法这个问题没有统一答案。在某些程序设计竞赛里数字字符串转换后前导零通常被自动忽略所以0123等同于123。但在另一些题意里要求“得到一个新的整数”那前导零虽然不影响整数值却会让输出格式变成0123不少评测系统会直接判错。稳妥的做法是如果题目没明确说允许前导零一律禁止首位替换成 0。如果明确说“输出可以是带有前导零的字符串”那就放开限制。我写了一个开关变量方便切换allow_leading_zero False在枚举时这样判断if i 0 and new_digit 0 and not allow_leading_zero: continue这样既能满足大多数题目的要求也能在特殊题目下快速调整。4.3 多解情况下怎么按“字典序最小”输出我遇到过一个变体题要求“输出所有方案中字典序最小的那个”或者“修改后数字最小”。这种多解问题的优先级需要分两层看第一层是修改位置第二层是数字大小。对于“数字最小”的目标修改位置的优先级其实要结合长度来看。因为等长字符串比较字典序就是从左到右逐位比较所以越靠左的位置越关键。换句话说你要先找一个最靠左的、可行修改位置中能让该位数最小的方案。我上面的代码采用“位置从前往后、数字从小到大”的枚举顺序第一个满足条件的解正好就是字典序最小的解。如果你要的是“修改后数字最大”只需把内层循环的数字顺序反转并且保持外层位置从前往后。因为相同长度下最高位越大整个数越大。这里容易犯的错误是有人先找所有可行解然后用int排序。一旦字符串很长转int又溢出了。正确做法是保持字符串比较。4.4 测试用例设计速查表我在本地跑测试时会固定用下面这一组用例防止自己漏掉边界。输入 n说明期望输出must_changeFalse1单数字非倍数77单数字且本身就是倍数7不改时/ 无解若强制改70原数是倍数且还有合法修改77若强制改/ 70不改时10首位为1个位为01412345普通测试比如 12348 或 12341取决于枚举顺序999999999999稳定大数自行计算重点验证不溢出777777777777大数本身 7 的倍数根据 must_change 判断我建议你把第一个用例1实测一下程序应返回 7因为7 - 1 6而这一位恰好是权值 1所以直接改个位即可。第二个用例7如果不允许不改代码会遍历完所有可能性后返回-1这一步能验证must_change分支是否正确。4.5 一个我曾经犯过的低级错误最让我印象深刻的错误是权值计算方向写反了。我一开始把第 i 位的权值算成了10^i mod 7而不是10^(len-1-i) mod 7。结果对于回文类数字刚好碰巧能过但换个普通数字就出错。调试了很久才发现字符串最高位对应的是最高次幂不是最低次幂。这个问题可以用一个非常小的例子验证n 21它本身能被 7 整除但如果我们把十位从2改成1得到11不是倍数把个位从1改成2得到22也不是倍数。所以21在“必须修改”的前提下无解。当我权值方向写反时代码会误以为某些修改可行。所以我建议写完后一定打印几个手算用例别只靠随机大数测试。5. 扩展思考如果要求“修改两个数”或者“求最少修改次数”5.1 从“改一位”到“改两位”的递推很多题目就是一个引子改一位做完后紧接着会让你做“允许修改两位”的版本。如果只改一位状态空间是len * 10。改两位直接枚举两重位置和两重数字会复杂到O(len^2 * 100)在长度大了之后跑不动。这时候可以用动态规划。比较通用的一种做法是“自动机 余数状态”用dp[i][j][k]表示处理到第 i 位时已经修改了 j 位当前整个数字前缀对 7 的余数为 k 时是否可行。转移时有两种选择不修改第 i 位直接沿用原数字余数变成(k * 10 old_digit) % 7修改第 i 位为新数字d则修改次数加 1余数变成(k * 10 d) % 7。最后只要看dp[len][m][0]是否为真就能知道是否可行同时记录路径输出方案。这个思路把“修改次数”限制在最多 2 次或 m 次复杂度是O(len * m * 7 * 10)对于 m 很小的情况非常高效。如果 m 很大那又是另一个背包问题了。5.2 如果要输出“所有可行解”怎么办有些场景不是找任意解而是想把所有可行修改都输出。简单做法就是把命中条件从return改成列表收集。但要注意最多可能有len * 9个合法结果首位最多 9 个数字其他位最多 10 个数字但要去掉原数字在len很大时输出本身就会爆量。通常面试或竞赛中不会要求输出全部解而只会要求输出字典序最小或最大的那个。因此代码里准备好一个“解比较函数”比把所有解都存下来更稳。你可以边枚举边保留当前最优解最后统一输出。5.3 扩展到“模数不是 7”时循环节会怎样这个题最漂亮的地方在于“7”看似随机实际上是精心选过的。如果你把模数换成 8、9 或者 11循环节长度也会跟着变。比如模 8 时10^k mod 8从 k0 开始是1, 2, 4, 0, 0, 0...但到后面全是 0这会让高位修改完全不影响余数。也就是说判断 8 的倍数时其实只需要看末三位修改高位根本没意义。模 11 时循环节是1, 10, 1, 10...也就是奇数位和偶数位分别起作用。所以判断 11 的倍数可以简化为“奇数位和与偶数位和的差”。如果你只想做一道题的解法直接用 7 的循环节即可。但如果你想真正理解这题的套路我建议把模数参数化写成函数solve_mod(n_str, mod)内部动态生成循环节。以后遇到判断 7 的倍数变体一行代码就能复用。我的实操心得这个题表面上是“简单修改一个 n”实际上考察的是大整数取模和权重思想。很多人第一眼觉得“这不就是枚举吗”但不写出完整代码很难发现首位限制、必须修改、多解优先级这些隐藏条件。我自己在写完后用随机大数和暴力法对拍过几百组数据确认循环节方向没错。这里也建议你写完代码后用random.randint生成一些十几位的数跑一版“直接转 int 暴力枚举”的代码做对比两边答案一致再收工。最后再分享一个小技巧如果你在面试里遇到这种题可以先问清楚三个问题。第一能否不修改就输出原数第二修改后能否有前导零第三多解时优先靠左还是靠右。把这三个问题问完不仅代码不会写歪面试官也会觉得你考虑周全。这道题本身不难但能把边界一次说清的人往往才是真把这个知识点吃透了。
