先说说这标题给我的第一感觉——“简单修改一个n让它变成7的倍数”乍一听像个脑筋急转弯但真上手做过的朋友都知道这里面藏着好几层坑。如果你是在刷算法题、做笔试或者纯粹想在Excel、数据库里把一串乱数字规整成能被7整除的数这道题几乎是绕不开的练手素材。它的本质是数字位置改动权限有限、目标整除关系明确、还得兼顾位数不丢稍微不留神就会掉进前导零、大数溢出、多解取舍这些暗坑里。我最早遇到这道题是在一场模拟笔试里题目大概是给一个很大的整数n只能改动其中某一位上的数字问能不能让它变成7的倍数能的话输出任意合法结果。乍一看很简单嘛暴力把每一位从0到9试一遍不就行了但真把代码写出来跑大数据就发现事情远没有那么简单。这篇文章就把我从暴力枚举到数学构造的完整思路、代码实现、踩坑记录都摊开聊一聊给还没做过这题的朋友一份能直接“抄作业”的参考。1. 拆解题目到底改“一个n”的什么1.1 三种常见的题目口径拿到“修改一个n让它变成7的倍数”这句话不同场景下其实暗含了三种完全不同的数学题稍不留神就会在理解上翻车。第一种口径对n任意加减一个数让它变成7的倍数。这种最简单算出n除以7的余数rn - r直接搞定。比如n 123123 ÷ 7 17余4123 - 4 119119 7 × 17完美。但这基本不含任何技术含量通常不会出现在正经题目里。第二种口径只能修改n的某一位数字且修改后数字位数不能变。这是绝大多数算法题、面试题采用的口径也是这篇文章的主线。比如n 12345我可以把十位上的4改成6得到12365验证一下12365 ÷ 7 1766余3不行改成7得到1237512375 ÷ 7 1767余6还是不行……就这么逐个试下去。注意“位数不能变”这个限制不是可有可无的——如果把最高位的1改成0数字就变成2345从五位数缩成四位数这在很多题目里是明令禁止的。第三种口径在第一种的基础上加约束比如只能改动一位、改动量要最小或者要求改动后的数字尽量大/尽量小。这类题本质上是第二种口径的变体只是在“多解”时额外指定了选择规则。所以拿到题目先别急着写代码先跟出题人确认口径。我见过不少人把“只能修改一位”理解成“可以加几万减几千”结果整个思路全偏了。1.2 数学本质余数、10的幂、模7不管哪种口径核心数学工具都是模运算。一个整数n能被7整除等价于 n mod 7 0。那“修改某一位”在模运算下意味着什么把n写成十进制展开n a[m] × 10^m a[m-1] × 10^(m-1) … a[1] × 10^1 a[0] × 10^0其中a[i]是一个0到9之间的数字。如果我把第k位上的数字从a[k]改成b那么新数n和原数n的差是n - n (b - a[k]) × 10^k所以n mod 7 (n mod 7) (b - a[k]) × 10^k mod 7。到这里问题的本质已经很清晰了我只需要两样东西——原数n除以7的余数r以及每个位置k对应的10^k除以7的余数d[k]。然后检查是否存在某个k和某个新数字b使得r (b - a[k]) × d[k] ≡ 0 (mod 7)这个公式看起来简单却是整个解题思路的分水岭。暴力枚举本质上就是在用这个公式做算草只不过它不直接解而是把所有候选结果都试一遍。而数学构造法则是直接反解出满足条件的b一步到位。1.3 为什么偏偏是7看到这里你可能会有个疑问为什么题目总是喜欢拿7做文章而不是2、5、10这些一眼能看出来的数原因很简单2和5只看末位4和8看末几位3和9看各位数字和这些都有非常直观的快速判定法。唯独7没有一个能在小学算术范围内轻松心算的判定式。虽然存在“截尾法”把个位截掉剩余数减去个位的两倍反复操作和“三位截断交替加减法”但操作繁琐远不如直接做除法来得快。正是这种“不方便”让7成了算法题里的常客——因为它逼着你使用通用的模运算框架而不是某个取巧的整除特征。同理11、13也经常被拿来当考点因为它们同样没有简单直观的倍数判定法。所以把这题的通用解法吃透相当于掌握了处理任意模数的通用范式以后再遇到“改成11的倍数”“改成13的倍数”把7换掉即可。2. 新手都能上手的暴力枚举法2.1 思路把数字当字符串逐位尝试0到9如果你只是想快速出答案不追求最高性能暴力枚举是最好理解、最不容易出错的办法。核心思路极其朴素把n转成字符串从最高位到最低位逐个位置尝试改成0到9每次改完检查一下新数字能不能被7整除能就返回不能就继续试。听着简单但实现里有几个容易忽略的细节。第一个是“第一位不能改成0”否则会减少数字位数第二个是“原位数字不用改”也就是如果当前那一位本来就是候选数字跳过或者直接检查原数是否已经是7的倍数第三个是“修改后如果还是负数或者前导零直接判非法”。我给出一个清晰直接的Python版本def make_divisible_by7(n_str: str): digits list(n_str) # 先检查原数本身是否已满足满足就不用改 if int(n_str) % 7 0: return n_str for i in range(len(digits)): original digits[i] for new_digit in 0123456789: if new_digit original: continue # 最高位不能改成0否则位数缩短 if i 0 and new_digit 0: continue digits[i] new_digit candidate int(.join(digits)) if candidate % 7 0: return .join(digits) digits[i] original # 还原继续下一轮 return None # 改一位无解 # 测试 print(make_divisible_by7(12345)) print(make_divisible_by7(100000000000000000001))这里我用了int(.join(digits))把字符串重新转回整数判断原因放在后面的“大数溢出”章节里讲。先记住测试数字如果超过C/C整型范围这行代码就是个雷点得换别的判断方式。2.2 复杂度与可行性分析这个暴力解法的时间复杂度是多少假设n有L位数字每位尝试0到9共10种可能所以要做的整除检查最多是 L × 10 次也就是 O(10L)跟数字位数成线性关系。对于L不超过十几位的普通数字这个复杂度可以忽略不计跑起来快到没感觉。但问题在于有很多题目给的n非常长可能是一百位、一千位的大整数超出常规整型的表示范围。这时候有两个瓶颈一是int类型溢出。C/C的long long最多表示大约19位十进制数Python的int虽然无上限但把几千位的字符串反复转成int再取模虽然功能上能做但性能并不理想而且其他主流语言根本扛不住。二是转int再判断整除本质上是对一个大整数做除法复杂度是O(L)乘上外层的10L次循环总复杂度O(10L²)。L大到1000时就是千万级别的运算虽然不至于卡死但显然有更优雅的解法。所以暴力法适合小数字、适合快速验证思路、适合作为标准答案的对照基准但不适合作为生产环境的最终方案。这也是为什么我坚持在掌握暴力的基础上还要学会下面的数学构造法。2.3 一个容易翻车的陷阱前导零暴力法里最高频的坑就是前导零。如果你不做任何限制直接把一个五位数的最高位从1改成0得到的“02345”在数学上等于四位数2345。有时候这个结果恰好能被7整除于是程序会开心地返回一个“看起来合法”的答案但题目如果要求不能改变位数这个答案就是错的。怎么排查两个办法一是在枚举时硬性跳过最高位改成0的情况代码里我已经加了这行二是在判断整除之前检查生成的字符串首位是否为0如果是就直接跳过。前者更高效后者更通用我推荐两个都写双保险。除了最高位还有一种隐蔽情况数字本身包含0比如1001把中间的0改成0看起来没改但确实执行了枚举要在逻辑里避免这种“无效修改”否则可能出现返回的字符串和原数一模一样的情况万一原数根本不是7的倍数那就属于逻辑漏洞了。3. 更漂亮的数学构造法一次判断O(10)求解3.1 推导核心公式diff × d ≡ -r (mod 7)暴力法虽然直观但总觉得“不够聪明”——明明每个位置只需要算出该改什么数字就行为什么要做10次试错数学构造法解决的就是这个问题。回到之前的公式。设r n mod 7第k位的原数字为a[k]新数字为b10^k mod 7 d[k]。条件r (b - a[k]) × d[k] ≡ 0 (mod 7)移项(b - a[k]) × d[k] ≡ -r (mod 7)令diff b - a[k]那么核心公式就是diff × d[k] ≡ -r (mod 7)这个公式是什么意思它把“这个位置改不改得动”变成了一个一次同余方程的求解问题。如果d[k]和7互质即d[k]不为0那diff在模7意义下有唯一解如果d[k] ≡ 0也就是10^k是7的倍数那不管怎么改这个位置对n的模7余数没有任何影响此时除非r自身为0原数已经是7的倍数否则这个位置永远改不成。这里有个关键洞察1到9之间diff的选择范围非常有限原数字a[k]不同候选diff也不同。我们可以直接对每个位置k枚举b 0到9检查是否满足等式这个枚举量和暴力法一样是10L但不需要构造完整数字、不需要做大数除法每一步都只是8以内的算术运算速度提升几个量级。3.2 10的幂对7的周期为什么只查循环表要想高效地使用这个公式得先把d[k] 10^k mod 7的规律摸清楚。我直接列出前几项k10^k10^k mod 70111103210023100064100004510000056100000017100000003注意到从k0到k5分别是1、3、2、6、4、5然后k6时回到1k7时回到3显然周期是6。所以根本不用算10的幂只需要一张6元素的循环表d[k] [1, 3, 2, 6, 4, 5][k mod 6]这个周期性不是巧合。根据费马小定理7是质数且10和7互质所以10^(7-1) ≡ 1 (mod 7)即10^6 ≡ 1 (mod 7)周期最多是6。事实上通过手算就能发现10^6 1000000除以7确实是999999的倍数余1完美闭合。为什么这个周期有用它让“计算10^k mod 7”这个操作从O(k)级别降到了O(1)级别。即使n有百万位我处理每一位时只需要看一眼它在十进制中的位置下标就知道对应的d[k]是多少全程没有任何大数计算。3.3 构造过程的完整走一遍n 12345理论讲太多容易晕拿个具体例子走一遍。设n 12345。先算r 12345 mod 7。用竖式除法或者心算7 × 1763 12341余4。所以r 4需要让新数满足 r ≡ 0 (mod 7)也就是要让改动带来的差贡献出 -4 ≡ 3 (mod 7)。接下来把数字按位拆开。12345从低位到高位第0位个位数字5d[0] 1。需要diff × 1 ≡ 3 (mod 7)即diff ≡ 3。b 5 3 8。把个位改成8得到12348验证12348 ÷ 7 1764整除成功。第1位十位数字4d[1] 3。需要diff × 3 ≡ 3diff ≡ 3 × 3^(-1) ≡ 3 × 5 ≡ 15 ≡ 1。b 4 1 5得到12354验证12354 ÷ 7 1764余6不对我重新算——12354 ÷ 7 1764.857不是整除。这说明中间有计算问题不公式是没问题的问题出在取模运算的符号上。注意diff × 3 ≡ 3 (mod 7)因为diff 1时1 × 3 3 ≡ 3没错。但得到b 5也符合“diff 1”啊。等一下我没检查b的范围——b必须是0到9之间的数字5是合法的。为什么12354不行再仔细一查发现原式是 r diff × d ≡ 0 (mod 7)即4 1 × 3 7 ≡ 0确实满足。但12354除以7算一下7 × 1765 12355所以12354 ≡ -1 ≡ 6并不是0。问题出在哪我重新推一遍。12345 a[0] a[1]×10 ...也就是5 4×10 3×100 2×1000 1×10000。把第1位即十位a[1] 4改成5新数变成12354。新旧之差12354 - 12345 (5 - 4) × 10 10而10 mod 7 3所以新数 mod 7 4 3 7 ≡ 0。本题应该成立啊我哪里算错了难道是12354真的能被7整除再算一次7 × 1765 12355少17 × 1764 12348多6。所以12354 ≡ -1是6不是0。那我逆推一遍。12345 7 × 1763 4所以12345 ≡ 4。要得到 ≡ 0差必须是7 × m - 4即 -4 ≡ 3 (mod 7)。我把第1位加1数值增加10十进制的10对应在模7下加3。4 3 7 ≡ 0。按理说应该是对的啊矛盾来了。唯一的解释是我前面把数字拆位搞错了。12345的十位不是“4”而是“4”没错。但等一下——12345 5 4×10 3×100 2×1000 1×10000这里4×10 40。把十位从4改成5增加的确实是10。原数12345改成12355我写错了我在前面写“新数12354”那其实是把十位从4改成5但百位动了不对12354 12345 9说明我改变了9而不是10。找到问题了12345的第1位十位是4改成5之后应该得到12355不是12354。我笔误把结果写成了12354导致验证失败。重新验证12355 ÷ 7 1765整除完美。刚才那一通折腾正好说明一个血泪教训——数学推导里的每一步输出都要仔细核对往往不是公式错而是抄错一位数。这个坑我在后面“常见问题”里还会专门提。继续往下走其他位置也类似第2位百位数字3d[2] 2。diff × 2 ≡ 3diff ≡ 3 × 4 ≡ 12 ≡ 5。b 3 5 8得到12845验证12845 ÷ 7 1835整除。第3位千位数字2d[3] 6。diff × 6 ≡ 3。6的模7乘法逆元是6因为6×636≡1所以diff ≡ 3 × 6 ≡ 18 ≡ 4。b 2 4 6得到16345验证16345 ÷ 7 2335整除。第4位万位数字1d[4] 4。diff × 4 ≡ 3diff ≡ 3 × 2 ≡ 6。b 1 6 7得到72345验证72345 ÷ 7 10335整除。你看每一个位置都能算出合法的改动方案。如果题目只要求输出任意一个结果枚举到第一个位置就可以返回实际耗时几乎为零。3.4 什么时候无解d[k] ≡ 0的特殊位置上面的例子所有位置都能改那你可能会觉得“是不是任何数都能改一位变成7的倍数”并不是。关键就在d[k] ≡ 0的特殊位置。哪些位置的10^k能被7整除回看循环表周期6的取值是1、3、2、6、4、5没有一个等于0。也就是说对任意非负整数k10^k mod 7永远不可能是0因为10和7互质10^k永远不可能被7整除。这个结论意味着在本题“只能改一位数字”的设定下理论上任何一个位置都具备改变整个数模7余数的能力不存在“这个位置怎么改都没用”的死角。那还会有无解的情况吗有但原因不是d[k] 0而是新数字b的取值范围受限。举例说明假设当前n mod 7 r某个位置原数字是a[k]d[k]对应的唯一diff为s。那么b a[k] s模7意义下。由于diff被限制在模7的0到6之间但实际数字差可以是-9到9之间的任意整数。如果满足条件的唯一b落在-9到9之外或者算出来b 0或b 9那这个位置就不能改。另外最高位改成0也是非法操作。更典型的一种无解场景是题目要求“只改动一位且改动量要最接近原始值差值的绝对值最小”。比如n mod 7 0时最“接近”的改动是改一个diff ≡ 0的位置但diff 0意味着实际上没改任何数字如果题目强制要求必须改动那就是无解。我在实现时会把“完全不改”作为一种特殊情况单独处理避免程序自相矛盾。4. 常见问题与排查技巧实录4.1 大数溢出字符串才是王道很多朋友第一次写这题时习惯用long long把数字存下来改一位再除一次。这个思路在小数字时没毛病但一旦n超过19位C/C里直接溢出C的__int128也最多吃下38位超过就束手无策。正确的做法是全程把n当作字符串处理。判断“修改某一位后能否被7整除”时要么用BigInteger类Java的BigIntegerPython的int天然无上限C#的System.Numerics.BigInteger要么干脆连大数都不构造只保留完整的模7余数。后者正是数学构造法的优势——我只需要在遍历字符串时维护当前整个数字的模7余数每一位乘上对应的d[k]累加即可全程不涉及任何超过8的整数运算。我建议的维护方式把字符串从高位到低位逐个处理用递推式 cur (cur × 10 digit) mod 7一遍扫描就能得到整个数的余数。这个操作对大数极其友好也不会因为语言限制翻车。4.2 前导零与位数变化前导零问题我在暴力法章节已经强调过一次这里从另一个角度再补一刀数学构造法虽然不直接构造新数但最终输出结果的时候还是要拼回字符串。如果你在某个位置算出的b 0而且这个位置恰好是最高位结果会是什么比如n 1234最高位1改成0输出0234这既不是合法数字表述也没有满足“不改变位数”的题设。所以在数学构造法中同样要加上最高位限制if i len(s)-1 and b 0: continue。别小看这行代码我在实际写的时候漏过一次结果返回了一个四位数冒充五位数被测试用例打得满头包。4.3 多解时该选哪个最小改动、数值最小、数值最大题目如果只要求“输出任意一个合法结果”那很简单从低位到高位找到第一个可行解直接返回。但很多变体题会追加让结果尽量大或尽量小的条件。如果要求“结果尽量大”优先改高位且在高位可行时选择最大的b。比如第4位原数字是1算出b可以是6那直接选6得到的72345显然比其它位置改动得到的数更大。如果要求“结果尽量小”优先改高位但选择最小的b。注意这并不等于改低位——改变低位对数值影响小但最小值的优先级是先改最高位的最小b。如果要求“改动幅度最小”即|新数 - 原数|最小规则又不一样优先改动低位且每位选择使差值绝对值最小的b。比如原数第0位是5可选b 8差值3和b 1差值4那选8。这三种排序规则我在面试里都遇到过每次都要仔细读题不要想当然地默认“输出任意解”就是最优解。4.4 自测用例表写代码容易验证难。这里分享一组我常用的自测用例覆盖各种边界情况输入预期的合理输出说明77已经是7的倍数无需改动87或14看改动限制改个位为7或1但不改变位数时8可以改成4或9等1414本身整除1000000000000任意可整除结果超大数测试不做大数转换499检查首位非0变化验证前导零限制0无解或返回0问清楚是否允许零本身一个一万位的随机字符串任意合法结果压测性能主要验证不卡死每个用例跑通之后我还会再用暴力法交叉验证一遍对随机小数字跑数学构造法和暴力枚举法比对两者的结果是否都能整除7结果是检验数学构造法正确性的最有效手段。5. 完整代码实现与两种方法对比5.1 Python实现数学构造法分享一份我实际测试可用的实现既精简又稳def try_modify(n_str: str): 修改n_str的一个数字使其成为7的倍数。 返回修改后的字符串无解返回None。 # 计算原数的模7余数 r 0 for ch in n_str: r (r * 10 int(ch)) % 7 if r 0: return n_str # 10^k mod 7 的循环表从k0开始 pow_mod [1, 3, 2, 6, 4, 5] # 2,3,4,5,6的逆元inverse[x] * x ≡ 1 mod 7 inv {1: 1, 2: 4, 3: 5, 4: 2, 5: 3, 6: 6} L len(n_str) digits list(map(int, n_str)) # 从低位到高位找最右边的可修改位这样改动幅度最小 for k in range(L): # k表示从右往左第几位即10^k pos L - 1 - k dk pow_mod[k % 6] # 需要 diff ≡ (-r) * inv(dk) (mod 7) need ((-r) * inv[dk]) % 7 original digits[pos] for new_digit in range(10): if new_digit original: continue # 最高位不能变成0 if pos 0 and new_digit 0: continue diff (new_digit - original) % 7 if diff need: digits[pos] new_digit return .join(map(str, digits)) # 无解则还原其实不还原也不影响因为后面不会再用到这个位置 return None这里有个设计细节值得多说一句need直接由(-r) * inv[dk] mod 7算出省去了逐个b试diff的循环。因为dk在1到6之间且和7互质模7乘法逆元一定存在。如果你不想用逆元也可以退回枚举b 0..9代码更直白但逆元思路更符合数学构造法的一步到位精神。5.2 暴力法和数学构造法的对比有人会觉得数学构造法似乎也没有特别省事枚举法不是也能10L解决问题吗确实在小数据量下两者都是瞬间完成但有几个维度的差异决定了生产环境中应该选谁对比项暴力枚举法数学构造法思路难度低新手友好中需要模运算基础大数处理能力弱需要BigInteger或频繁构造大数据强全程只用小整数运算时间复杂度O(L²)反复构造大数做整除O(L)一遍扫描每个位置常数操作多解优化麻烦需要额外逻辑判断自然直接控制遍历顺序和b取值出错率高字符串还原、前导零、溢出低只要处理好最高位限制即可代码量少但逻辑分散略多但集中我个人的建议是如果你在写比赛或笔试代码时间紧凑对模运算又有信心直接上数学构造法如果你是初学第一次接触这类题先写暴力版本验证思路再升级成数学版本这样既能确认理解正确也能看到优化前后的变化。5.3 扩展到任意模数把7替换成13会怎样这套方法最值钱的地方在于它完全通用。把7换成任意其他质数只需要改三个地方周期表换成新的乘法群的循环周期。比如换成1110 ≡ -1 (mod 11)所以10^k mod 11交替为1和-1周期2换成13根据费马小定理周期最多12实际计算10^1 mod 13 1010^2 910^3 12之后循环。求逆元。模数变了1到m-1之间的乘法逆元表也要跟着换。仍然用扩展欧几里得算法求即可。最高位限制不变但要注意其他位的位数缩减规则也不变。换成合数比如6、10、12时情况略特殊某些位置的10^k可能与模数不互质导致不存在逆元此时要么用枚举法要么用更广义的一次同余方程求解先除公约数再求逆元。这个问题延伸开去能写一整篇文章这里点到为止给想深入的朋友留个线索。6. 实操总结与个人心得把整道题做完一遍我的直观感受是数学构造法的核心优势不在于“更短”而在于“不需要构造大数本身”。尤其是面对几千位的超长数据暴力枚举法每次试错都要把整个字符串拼一遍、算一遍除法时间全花在造轮子上了而构造法只关心“差了多少余数”跟数字本身长什么样完全解耦。另一个让我印象深刻的地方是模逆元的普适性。很多初学者看到需要求逆元就打退堂鼓觉得那是数论高深内容。但实际上针对7这样的质数你可以用循环把1到6的逆元全手算出来甚至直接用枚举法代替逆元运算。写代码时先用枚举实现测试通过后再用逆元优化整个过程对数学背景要求极低。最后分享一个我在实际开发中踩过的坑有一版实现里我把遍历顺序写成了“从高位到低位”导致输出总是一个很大的改动比如把第一位从1改成9虽然每题都能过但一旦遇到“输出改动最小的方案”这类变体就全线崩溃。后来我改成从低位k 0开始搜索默认就能输出改动幅度最小的解正好契合大多数题目的隐含要求。这个细节改完后同样的核心逻辑能适应多种评分标准省下了不少反复调整的时间。如果你正准备应付笔试里的这类整除构造题我的建议是先照着上面的代码在自己本地跑一遍把前导零、溢出、多解三条边界全部测一遍再把7换成11、13各做一题找找手感。做到这一步再遇到“简单修改一个n让它变成X的倍数”这类问题对你来说就真的只是改一行参数的事了。
修改一个数字使其成为7的倍数：从暴力枚举到数学构造
先说说这标题给我的第一感觉——“简单修改一个n让它变成7的倍数”乍一听像个脑筋急转弯但真上手做过的朋友都知道这里面藏着好几层坑。如果你是在刷算法题、做笔试或者纯粹想在Excel、数据库里把一串乱数字规整成能被7整除的数这道题几乎是绕不开的练手素材。它的本质是数字位置改动权限有限、目标整除关系明确、还得兼顾位数不丢稍微不留神就会掉进前导零、大数溢出、多解取舍这些暗坑里。我最早遇到这道题是在一场模拟笔试里题目大概是给一个很大的整数n只能改动其中某一位上的数字问能不能让它变成7的倍数能的话输出任意合法结果。乍一看很简单嘛暴力把每一位从0到9试一遍不就行了但真把代码写出来跑大数据就发现事情远没有那么简单。这篇文章就把我从暴力枚举到数学构造的完整思路、代码实现、踩坑记录都摊开聊一聊给还没做过这题的朋友一份能直接“抄作业”的参考。1. 拆解题目到底改“一个n”的什么1.1 三种常见的题目口径拿到“修改一个n让它变成7的倍数”这句话不同场景下其实暗含了三种完全不同的数学题稍不留神就会在理解上翻车。第一种口径对n任意加减一个数让它变成7的倍数。这种最简单算出n除以7的余数rn - r直接搞定。比如n 123123 ÷ 7 17余4123 - 4 119119 7 × 17完美。但这基本不含任何技术含量通常不会出现在正经题目里。第二种口径只能修改n的某一位数字且修改后数字位数不能变。这是绝大多数算法题、面试题采用的口径也是这篇文章的主线。比如n 12345我可以把十位上的4改成6得到12365验证一下12365 ÷ 7 1766余3不行改成7得到1237512375 ÷ 7 1767余6还是不行……就这么逐个试下去。注意“位数不能变”这个限制不是可有可无的——如果把最高位的1改成0数字就变成2345从五位数缩成四位数这在很多题目里是明令禁止的。第三种口径在第一种的基础上加约束比如只能改动一位、改动量要最小或者要求改动后的数字尽量大/尽量小。这类题本质上是第二种口径的变体只是在“多解”时额外指定了选择规则。所以拿到题目先别急着写代码先跟出题人确认口径。我见过不少人把“只能修改一位”理解成“可以加几万减几千”结果整个思路全偏了。1.2 数学本质余数、10的幂、模7不管哪种口径核心数学工具都是模运算。一个整数n能被7整除等价于 n mod 7 0。那“修改某一位”在模运算下意味着什么把n写成十进制展开n a[m] × 10^m a[m-1] × 10^(m-1) … a[1] × 10^1 a[0] × 10^0其中a[i]是一个0到9之间的数字。如果我把第k位上的数字从a[k]改成b那么新数n和原数n的差是n - n (b - a[k]) × 10^k所以n mod 7 (n mod 7) (b - a[k]) × 10^k mod 7。到这里问题的本质已经很清晰了我只需要两样东西——原数n除以7的余数r以及每个位置k对应的10^k除以7的余数d[k]。然后检查是否存在某个k和某个新数字b使得r (b - a[k]) × d[k] ≡ 0 (mod 7)这个公式看起来简单却是整个解题思路的分水岭。暴力枚举本质上就是在用这个公式做算草只不过它不直接解而是把所有候选结果都试一遍。而数学构造法则是直接反解出满足条件的b一步到位。1.3 为什么偏偏是7看到这里你可能会有个疑问为什么题目总是喜欢拿7做文章而不是2、5、10这些一眼能看出来的数原因很简单2和5只看末位4和8看末几位3和9看各位数字和这些都有非常直观的快速判定法。唯独7没有一个能在小学算术范围内轻松心算的判定式。虽然存在“截尾法”把个位截掉剩余数减去个位的两倍反复操作和“三位截断交替加减法”但操作繁琐远不如直接做除法来得快。正是这种“不方便”让7成了算法题里的常客——因为它逼着你使用通用的模运算框架而不是某个取巧的整除特征。同理11、13也经常被拿来当考点因为它们同样没有简单直观的倍数判定法。所以把这题的通用解法吃透相当于掌握了处理任意模数的通用范式以后再遇到“改成11的倍数”“改成13的倍数”把7换掉即可。2. 新手都能上手的暴力枚举法2.1 思路把数字当字符串逐位尝试0到9如果你只是想快速出答案不追求最高性能暴力枚举是最好理解、最不容易出错的办法。核心思路极其朴素把n转成字符串从最高位到最低位逐个位置尝试改成0到9每次改完检查一下新数字能不能被7整除能就返回不能就继续试。听着简单但实现里有几个容易忽略的细节。第一个是“第一位不能改成0”否则会减少数字位数第二个是“原位数字不用改”也就是如果当前那一位本来就是候选数字跳过或者直接检查原数是否已经是7的倍数第三个是“修改后如果还是负数或者前导零直接判非法”。我给出一个清晰直接的Python版本def make_divisible_by7(n_str: str): digits list(n_str) # 先检查原数本身是否已满足满足就不用改 if int(n_str) % 7 0: return n_str for i in range(len(digits)): original digits[i] for new_digit in 0123456789: if new_digit original: continue # 最高位不能改成0否则位数缩短 if i 0 and new_digit 0: continue digits[i] new_digit candidate int(.join(digits)) if candidate % 7 0: return .join(digits) digits[i] original # 还原继续下一轮 return None # 改一位无解 # 测试 print(make_divisible_by7(12345)) print(make_divisible_by7(100000000000000000001))这里我用了int(.join(digits))把字符串重新转回整数判断原因放在后面的“大数溢出”章节里讲。先记住测试数字如果超过C/C整型范围这行代码就是个雷点得换别的判断方式。2.2 复杂度与可行性分析这个暴力解法的时间复杂度是多少假设n有L位数字每位尝试0到9共10种可能所以要做的整除检查最多是 L × 10 次也就是 O(10L)跟数字位数成线性关系。对于L不超过十几位的普通数字这个复杂度可以忽略不计跑起来快到没感觉。但问题在于有很多题目给的n非常长可能是一百位、一千位的大整数超出常规整型的表示范围。这时候有两个瓶颈一是int类型溢出。C/C的long long最多表示大约19位十进制数Python的int虽然无上限但把几千位的字符串反复转成int再取模虽然功能上能做但性能并不理想而且其他主流语言根本扛不住。二是转int再判断整除本质上是对一个大整数做除法复杂度是O(L)乘上外层的10L次循环总复杂度O(10L²)。L大到1000时就是千万级别的运算虽然不至于卡死但显然有更优雅的解法。所以暴力法适合小数字、适合快速验证思路、适合作为标准答案的对照基准但不适合作为生产环境的最终方案。这也是为什么我坚持在掌握暴力的基础上还要学会下面的数学构造法。2.3 一个容易翻车的陷阱前导零暴力法里最高频的坑就是前导零。如果你不做任何限制直接把一个五位数的最高位从1改成0得到的“02345”在数学上等于四位数2345。有时候这个结果恰好能被7整除于是程序会开心地返回一个“看起来合法”的答案但题目如果要求不能改变位数这个答案就是错的。怎么排查两个办法一是在枚举时硬性跳过最高位改成0的情况代码里我已经加了这行二是在判断整除之前检查生成的字符串首位是否为0如果是就直接跳过。前者更高效后者更通用我推荐两个都写双保险。除了最高位还有一种隐蔽情况数字本身包含0比如1001把中间的0改成0看起来没改但确实执行了枚举要在逻辑里避免这种“无效修改”否则可能出现返回的字符串和原数一模一样的情况万一原数根本不是7的倍数那就属于逻辑漏洞了。3. 更漂亮的数学构造法一次判断O(10)求解3.1 推导核心公式diff × d ≡ -r (mod 7)暴力法虽然直观但总觉得“不够聪明”——明明每个位置只需要算出该改什么数字就行为什么要做10次试错数学构造法解决的就是这个问题。回到之前的公式。设r n mod 7第k位的原数字为a[k]新数字为b10^k mod 7 d[k]。条件r (b - a[k]) × d[k] ≡ 0 (mod 7)移项(b - a[k]) × d[k] ≡ -r (mod 7)令diff b - a[k]那么核心公式就是diff × d[k] ≡ -r (mod 7)这个公式是什么意思它把“这个位置改不改得动”变成了一个一次同余方程的求解问题。如果d[k]和7互质即d[k]不为0那diff在模7意义下有唯一解如果d[k] ≡ 0也就是10^k是7的倍数那不管怎么改这个位置对n的模7余数没有任何影响此时除非r自身为0原数已经是7的倍数否则这个位置永远改不成。这里有个关键洞察1到9之间diff的选择范围非常有限原数字a[k]不同候选diff也不同。我们可以直接对每个位置k枚举b 0到9检查是否满足等式这个枚举量和暴力法一样是10L但不需要构造完整数字、不需要做大数除法每一步都只是8以内的算术运算速度提升几个量级。3.2 10的幂对7的周期为什么只查循环表要想高效地使用这个公式得先把d[k] 10^k mod 7的规律摸清楚。我直接列出前几项k10^k10^k mod 70111103210023100064100004510000056100000017100000003注意到从k0到k5分别是1、3、2、6、4、5然后k6时回到1k7时回到3显然周期是6。所以根本不用算10的幂只需要一张6元素的循环表d[k] [1, 3, 2, 6, 4, 5][k mod 6]这个周期性不是巧合。根据费马小定理7是质数且10和7互质所以10^(7-1) ≡ 1 (mod 7)即10^6 ≡ 1 (mod 7)周期最多是6。事实上通过手算就能发现10^6 1000000除以7确实是999999的倍数余1完美闭合。为什么这个周期有用它让“计算10^k mod 7”这个操作从O(k)级别降到了O(1)级别。即使n有百万位我处理每一位时只需要看一眼它在十进制中的位置下标就知道对应的d[k]是多少全程没有任何大数计算。3.3 构造过程的完整走一遍n 12345理论讲太多容易晕拿个具体例子走一遍。设n 12345。先算r 12345 mod 7。用竖式除法或者心算7 × 1763 12341余4。所以r 4需要让新数满足 r ≡ 0 (mod 7)也就是要让改动带来的差贡献出 -4 ≡ 3 (mod 7)。接下来把数字按位拆开。12345从低位到高位第0位个位数字5d[0] 1。需要diff × 1 ≡ 3 (mod 7)即diff ≡ 3。b 5 3 8。把个位改成8得到12348验证12348 ÷ 7 1764整除成功。第1位十位数字4d[1] 3。需要diff × 3 ≡ 3diff ≡ 3 × 3^(-1) ≡ 3 × 5 ≡ 15 ≡ 1。b 4 1 5得到12354验证12354 ÷ 7 1764余6不对我重新算——12354 ÷ 7 1764.857不是整除。这说明中间有计算问题不公式是没问题的问题出在取模运算的符号上。注意diff × 3 ≡ 3 (mod 7)因为diff 1时1 × 3 3 ≡ 3没错。但得到b 5也符合“diff 1”啊。等一下我没检查b的范围——b必须是0到9之间的数字5是合法的。为什么12354不行再仔细一查发现原式是 r diff × d ≡ 0 (mod 7)即4 1 × 3 7 ≡ 0确实满足。但12354除以7算一下7 × 1765 12355所以12354 ≡ -1 ≡ 6并不是0。问题出在哪我重新推一遍。12345 a[0] a[1]×10 ...也就是5 4×10 3×100 2×1000 1×10000。把第1位即十位a[1] 4改成5新数变成12354。新旧之差12354 - 12345 (5 - 4) × 10 10而10 mod 7 3所以新数 mod 7 4 3 7 ≡ 0。本题应该成立啊我哪里算错了难道是12354真的能被7整除再算一次7 × 1765 12355少17 × 1764 12348多6。所以12354 ≡ -1是6不是0。那我逆推一遍。12345 7 × 1763 4所以12345 ≡ 4。要得到 ≡ 0差必须是7 × m - 4即 -4 ≡ 3 (mod 7)。我把第1位加1数值增加10十进制的10对应在模7下加3。4 3 7 ≡ 0。按理说应该是对的啊矛盾来了。唯一的解释是我前面把数字拆位搞错了。12345的十位不是“4”而是“4”没错。但等一下——12345 5 4×10 3×100 2×1000 1×10000这里4×10 40。把十位从4改成5增加的确实是10。原数12345改成12355我写错了我在前面写“新数12354”那其实是把十位从4改成5但百位动了不对12354 12345 9说明我改变了9而不是10。找到问题了12345的第1位十位是4改成5之后应该得到12355不是12354。我笔误把结果写成了12354导致验证失败。重新验证12355 ÷ 7 1765整除完美。刚才那一通折腾正好说明一个血泪教训——数学推导里的每一步输出都要仔细核对往往不是公式错而是抄错一位数。这个坑我在后面“常见问题”里还会专门提。继续往下走其他位置也类似第2位百位数字3d[2] 2。diff × 2 ≡ 3diff ≡ 3 × 4 ≡ 12 ≡ 5。b 3 5 8得到12845验证12845 ÷ 7 1835整除。第3位千位数字2d[3] 6。diff × 6 ≡ 3。6的模7乘法逆元是6因为6×636≡1所以diff ≡ 3 × 6 ≡ 18 ≡ 4。b 2 4 6得到16345验证16345 ÷ 7 2335整除。第4位万位数字1d[4] 4。diff × 4 ≡ 3diff ≡ 3 × 2 ≡ 6。b 1 6 7得到72345验证72345 ÷ 7 10335整除。你看每一个位置都能算出合法的改动方案。如果题目只要求输出任意一个结果枚举到第一个位置就可以返回实际耗时几乎为零。3.4 什么时候无解d[k] ≡ 0的特殊位置上面的例子所有位置都能改那你可能会觉得“是不是任何数都能改一位变成7的倍数”并不是。关键就在d[k] ≡ 0的特殊位置。哪些位置的10^k能被7整除回看循环表周期6的取值是1、3、2、6、4、5没有一个等于0。也就是说对任意非负整数k10^k mod 7永远不可能是0因为10和7互质10^k永远不可能被7整除。这个结论意味着在本题“只能改一位数字”的设定下理论上任何一个位置都具备改变整个数模7余数的能力不存在“这个位置怎么改都没用”的死角。那还会有无解的情况吗有但原因不是d[k] 0而是新数字b的取值范围受限。举例说明假设当前n mod 7 r某个位置原数字是a[k]d[k]对应的唯一diff为s。那么b a[k] s模7意义下。由于diff被限制在模7的0到6之间但实际数字差可以是-9到9之间的任意整数。如果满足条件的唯一b落在-9到9之外或者算出来b 0或b 9那这个位置就不能改。另外最高位改成0也是非法操作。更典型的一种无解场景是题目要求“只改动一位且改动量要最接近原始值差值的绝对值最小”。比如n mod 7 0时最“接近”的改动是改一个diff ≡ 0的位置但diff 0意味着实际上没改任何数字如果题目强制要求必须改动那就是无解。我在实现时会把“完全不改”作为一种特殊情况单独处理避免程序自相矛盾。4. 常见问题与排查技巧实录4.1 大数溢出字符串才是王道很多朋友第一次写这题时习惯用long long把数字存下来改一位再除一次。这个思路在小数字时没毛病但一旦n超过19位C/C里直接溢出C的__int128也最多吃下38位超过就束手无策。正确的做法是全程把n当作字符串处理。判断“修改某一位后能否被7整除”时要么用BigInteger类Java的BigIntegerPython的int天然无上限C#的System.Numerics.BigInteger要么干脆连大数都不构造只保留完整的模7余数。后者正是数学构造法的优势——我只需要在遍历字符串时维护当前整个数字的模7余数每一位乘上对应的d[k]累加即可全程不涉及任何超过8的整数运算。我建议的维护方式把字符串从高位到低位逐个处理用递推式 cur (cur × 10 digit) mod 7一遍扫描就能得到整个数的余数。这个操作对大数极其友好也不会因为语言限制翻车。4.2 前导零与位数变化前导零问题我在暴力法章节已经强调过一次这里从另一个角度再补一刀数学构造法虽然不直接构造新数但最终输出结果的时候还是要拼回字符串。如果你在某个位置算出的b 0而且这个位置恰好是最高位结果会是什么比如n 1234最高位1改成0输出0234这既不是合法数字表述也没有满足“不改变位数”的题设。所以在数学构造法中同样要加上最高位限制if i len(s)-1 and b 0: continue。别小看这行代码我在实际写的时候漏过一次结果返回了一个四位数冒充五位数被测试用例打得满头包。4.3 多解时该选哪个最小改动、数值最小、数值最大题目如果只要求“输出任意一个合法结果”那很简单从低位到高位找到第一个可行解直接返回。但很多变体题会追加让结果尽量大或尽量小的条件。如果要求“结果尽量大”优先改高位且在高位可行时选择最大的b。比如第4位原数字是1算出b可以是6那直接选6得到的72345显然比其它位置改动得到的数更大。如果要求“结果尽量小”优先改高位但选择最小的b。注意这并不等于改低位——改变低位对数值影响小但最小值的优先级是先改最高位的最小b。如果要求“改动幅度最小”即|新数 - 原数|最小规则又不一样优先改动低位且每位选择使差值绝对值最小的b。比如原数第0位是5可选b 8差值3和b 1差值4那选8。这三种排序规则我在面试里都遇到过每次都要仔细读题不要想当然地默认“输出任意解”就是最优解。4.4 自测用例表写代码容易验证难。这里分享一组我常用的自测用例覆盖各种边界情况输入预期的合理输出说明77已经是7的倍数无需改动87或14看改动限制改个位为7或1但不改变位数时8可以改成4或9等1414本身整除1000000000000任意可整除结果超大数测试不做大数转换499检查首位非0变化验证前导零限制0无解或返回0问清楚是否允许零本身一个一万位的随机字符串任意合法结果压测性能主要验证不卡死每个用例跑通之后我还会再用暴力法交叉验证一遍对随机小数字跑数学构造法和暴力枚举法比对两者的结果是否都能整除7结果是检验数学构造法正确性的最有效手段。5. 完整代码实现与两种方法对比5.1 Python实现数学构造法分享一份我实际测试可用的实现既精简又稳def try_modify(n_str: str): 修改n_str的一个数字使其成为7的倍数。 返回修改后的字符串无解返回None。 # 计算原数的模7余数 r 0 for ch in n_str: r (r * 10 int(ch)) % 7 if r 0: return n_str # 10^k mod 7 的循环表从k0开始 pow_mod [1, 3, 2, 6, 4, 5] # 2,3,4,5,6的逆元inverse[x] * x ≡ 1 mod 7 inv {1: 1, 2: 4, 3: 5, 4: 2, 5: 3, 6: 6} L len(n_str) digits list(map(int, n_str)) # 从低位到高位找最右边的可修改位这样改动幅度最小 for k in range(L): # k表示从右往左第几位即10^k pos L - 1 - k dk pow_mod[k % 6] # 需要 diff ≡ (-r) * inv(dk) (mod 7) need ((-r) * inv[dk]) % 7 original digits[pos] for new_digit in range(10): if new_digit original: continue # 最高位不能变成0 if pos 0 and new_digit 0: continue diff (new_digit - original) % 7 if diff need: digits[pos] new_digit return .join(map(str, digits)) # 无解则还原其实不还原也不影响因为后面不会再用到这个位置 return None这里有个设计细节值得多说一句need直接由(-r) * inv[dk] mod 7算出省去了逐个b试diff的循环。因为dk在1到6之间且和7互质模7乘法逆元一定存在。如果你不想用逆元也可以退回枚举b 0..9代码更直白但逆元思路更符合数学构造法的一步到位精神。5.2 暴力法和数学构造法的对比有人会觉得数学构造法似乎也没有特别省事枚举法不是也能10L解决问题吗确实在小数据量下两者都是瞬间完成但有几个维度的差异决定了生产环境中应该选谁对比项暴力枚举法数学构造法思路难度低新手友好中需要模运算基础大数处理能力弱需要BigInteger或频繁构造大数据强全程只用小整数运算时间复杂度O(L²)反复构造大数做整除O(L)一遍扫描每个位置常数操作多解优化麻烦需要额外逻辑判断自然直接控制遍历顺序和b取值出错率高字符串还原、前导零、溢出低只要处理好最高位限制即可代码量少但逻辑分散略多但集中我个人的建议是如果你在写比赛或笔试代码时间紧凑对模运算又有信心直接上数学构造法如果你是初学第一次接触这类题先写暴力版本验证思路再升级成数学版本这样既能确认理解正确也能看到优化前后的变化。5.3 扩展到任意模数把7替换成13会怎样这套方法最值钱的地方在于它完全通用。把7换成任意其他质数只需要改三个地方周期表换成新的乘法群的循环周期。比如换成1110 ≡ -1 (mod 11)所以10^k mod 11交替为1和-1周期2换成13根据费马小定理周期最多12实际计算10^1 mod 13 1010^2 910^3 12之后循环。求逆元。模数变了1到m-1之间的乘法逆元表也要跟着换。仍然用扩展欧几里得算法求即可。最高位限制不变但要注意其他位的位数缩减规则也不变。换成合数比如6、10、12时情况略特殊某些位置的10^k可能与模数不互质导致不存在逆元此时要么用枚举法要么用更广义的一次同余方程求解先除公约数再求逆元。这个问题延伸开去能写一整篇文章这里点到为止给想深入的朋友留个线索。6. 实操总结与个人心得把整道题做完一遍我的直观感受是数学构造法的核心优势不在于“更短”而在于“不需要构造大数本身”。尤其是面对几千位的超长数据暴力枚举法每次试错都要把整个字符串拼一遍、算一遍除法时间全花在造轮子上了而构造法只关心“差了多少余数”跟数字本身长什么样完全解耦。另一个让我印象深刻的地方是模逆元的普适性。很多初学者看到需要求逆元就打退堂鼓觉得那是数论高深内容。但实际上针对7这样的质数你可以用循环把1到6的逆元全手算出来甚至直接用枚举法代替逆元运算。写代码时先用枚举实现测试通过后再用逆元优化整个过程对数学背景要求极低。最后分享一个我在实际开发中踩过的坑有一版实现里我把遍历顺序写成了“从高位到低位”导致输出总是一个很大的改动比如把第一位从1改成9虽然每题都能过但一旦遇到“输出改动最小的方案”这类变体就全线崩溃。后来我改成从低位k 0开始搜索默认就能输出改动幅度最小的解正好契合大多数题目的隐含要求。这个细节改完后同样的核心逻辑能适应多种评分标准省下了不少反复调整的时间。如果你正准备应付笔试里的这类整除构造题我的建议是先照着上面的代码在自己本地跑一遍把前导零、溢出、多解三条边界全部测一遍再把7换成11、13各做一题找找手感。做到这一步再遇到“简单修改一个n让它变成X的倍数”这类问题对你来说就真的只是改一行参数的事了。
