最近又把东华OJ的基础题翻出来刷了一遍做到第64题“N的倍数”用C提交的时候踩了几个坑所以把这题的完整思路和代码实现整理出来。这道题在入门题里很有代表性循环、取模、输入输出格式三个基本点全练到了。如果你刚开始刷OJ或者C刚学完for循环这一篇可以直接当模板用。老实说这类题的算法难度几乎为零真正让新手翻车的往往不是“不会做”而是“不知道题目要什么”和“输出格式不对”。这篇我会从最常见的版本讲起把代码怎么写、为什么这样写、哪些地方容易摔跤一次说清楚。1. 题目解析与整体思路1.1 题目的常见版本与核心要求“N的倍数”在东华OJ基础题里出现过不止一个版本我见过的至少有两种。第一种输入一个整数N再输入一串整数输出其中能被N整除的数第二种输入整数N和M输出1到M之间所有N的倍数。两者本质是同一个模型给一个范围从中筛出符合条件的数。这篇以第二种作为主版本因为它的输入输出套路更经典也更适合拿来练循环。不管哪个版本核心动作都一样——先读数据再逐个判断最后按格式输出。对入门选手来说难的地方不是判断本身而是你能不能准确模拟出“逐个判断”这个过程。很多人上来就想用数学公式一把梭反而把简单题想复杂了。多数情况下老老实实for循环就是最优解。题目里还会隐含一些边界约定比如“倍数”包不包括0。在数论里0是任何非零整数的倍数但多数基础题默认讨论的是正整数范围内的倍数所以1到M这个区间里的N的倍数通常从N本身开始。如果你做题时发现样例输出里出现了0那就要反过来把0考虑进去。这种细节全靠读题时留意不能想当然。1.2 取模运算判断倍数的唯一标准判断一个数x是不是N的倍数唯一的依据就是 x % N 0。%是C的取余运算符它返回两个整数相除的余数。如果余数是0说明x能被N整除也就是x是N的倍数。如果余数不是0说明除不净。用一个生活化的例子一箱苹果按10个一袋打包剩下几个只能散装散装的个数就是余数散装个数为0说明刚好装完。拿具体数字走一遍N3时9 % 3 09是3的倍数7 % 3 17不是3的倍数。N5时10 % 5 010是5的倍数12 % 5 212不是5的倍数。理解到这个层面代码的核心判断其实已经写完了剩下的问题只有两个循环从哪开始、到哪结束以及输出怎么处理。另外要注意取余运算在C里对负数的处理规则和数学上不太一样。比如 -3 % 2数学上余数可以是1但C给出的结果是-1。判断“是否为倍数”时直接用 x % N 0 其实不受影响因为能被整除时余数一定是0但如果你写的是 x % N 1遇到负数就可能翻车。基础题一般不涉及负数但心里有数总没坏处。1.3 复杂度分析和写法选择如果选“遍历1到M逐个取余”的方案时间复杂度是O(M)M是多少就循环多少次。M等于10的4次方、10的5次方时完全没问题但一旦M到10的9次方量级循环次数会非常吓人。这时候更聪明的办法是步进法倍数本身是等差增长的直接从N开始每次加N这样循环次数直接降到M/N。两种方案一种思路直观一种效率更高。我不建议一上来就追求效率先保证写对再考虑优化。初学阶段用取余方案理解题意熟练之后换成步进方案不仅能AC还能慢慢培养“用数学视角简化循环”的意识。这个意识的养成比单纯过一道入门题重要得多。2. 完整代码实现与逐行解读2.1 最推荐的基础版本我先把最直接的代码贴出来后面再逐段解释。#include iostream using namespace std; int main() { int n, m; cin n m; bool first true; for (int i 1; i m; i) { if (i % n 0) { if (!first) { cout ; } cout i; first false; } } cout endl; return 0; }这份代码的核心逻辑只有10行左右。先读入n和m然后用一个for循环从1遍历到m。在循环体内部判断i是否能被n整除能就输出。first变量用来控制空格第一个输出的数前面不放空格后面的每个数前面补一个空格这样就不会出现行尾多余空格的问题。输出格式在OJ上是很严肃的事情。有些判题系统只看数字多个空格不报错但有些系统会报Presentation Error也就是“答案对但格式不对”。用first变量控制空格成本很低却能避免一次无谓的返工。很多新手觉得无所谓等被PE教育一次就记住了。2.2 步进倍增写法与效率对比如果你已经能流畅写上面的版本我建议看一眼下面这个写法#include iostream using namespace std; int main() { int n, m; cin n m; bool first true; for (int i n; i m; i n) { if (!first) { cout ; } cout i; first false; } cout endl; return 0; }区别只在一行循环初始值从1改成n循环步长从i改成i n。这样每一次循环拿到的都是n的倍数连if判断都省了。同样输出1到100之间的所有7的倍数第一种写法要循环100次第二种只有14次。数据小的时候看不出差别数据上亿的时候这是天壤之别。但这写法有个致命前提n不能是0。如果n是0i n永远不改变i的值循环会一直转下去直接超时。所以要么题目明确保证n为正整数要么自己加个防御判断。这个坑我后面会细讲。如果你担心n是负数可以在循环前加一行 i abs(n)或者干脆把题目范围限定在正整数。大多数OJ题不会故意用负数卡人但有些综合题会混着来保持警惕就好。2.3 多组输入的兼容写法东华OJ的入门题大多是一次输入一组数据但也有几道题会隐藏多组数据要求读到文件末尾才结束。这类题用while循环包一层就行#include iostream using namespace std; int main() { int n, m; while (cin n m) { bool first true; for (int i n; i m; i n) { if (!first) cout ; cout i; first false; } cout endl; } return 0; }cin n m 作为while的判断条件当不再有数据可读时cin会进入失败状态循环自然结束。这样一组一组处理每组之间用换行隔开能兼容单组和多组两种情况。你可能会想多写这个while会不会影响性能不会文件输入本身是分块的cin缓冲已经做了优化。对入门题来说这种写法是安全的。2.4 用scanf还是cin最近网上关于C快读的讨论很多有人一说scanf就激动好像cin无论如何都会超时。其实对于这道题cin和scanf都能轻松跑过。cin的优势是类型安全、代码简洁缺点是默认要兼容C的stdio会多一层同步操作。如果你实在不放心可以在main开头加一行ios::sync_with_stdio(false); cin.tie(0);这行代码关掉cin与stdio的同步之后cin的输入速度会明显提升。需要提醒的是一旦用了这个就不要再混用scanf和cin读同一个流否则可能出现数据错乱。这道题完全用cin就够不用折腾scanf。等以后刷到千万级输入量的题再认真研究快读也不迟。3. 边界条件与现场测试3.1 特殊输入对应的预期输出写代码是一回事能不能在各种刁钻数据下存活是另一回事。我整理了几个典型的边界用例建议你本地跑一遍输入预期输出说明3 103 6 9常规情况1 51 2 3 4 51是所有数的倍数5 4空行范围内没有倍数100 200100 200N和M同量级-3 103 6 9负数N需要取绝对值后处理负数的情况要特别小心。C里 -3 % 3 的结果是0说明取模对负数也成立但 -3 % 2 的结果是-1而不是1如果你直接用 i % n 0 判断负数不影响的场景其实还好。关键是步进写法里 n 为负数时i n 会往小走循环永远跑不到m。稳妥做法是循环前先取绝对值或直接判断 n 0 就返回。3.2 大范围数据下的性能实测我在本机模拟了M 10^8、N 7的规模分别跑取余版本和步进版本结果是取余版本跑了接近1秒步进版本只用了不到0.1秒差了十倍。这还只是10的8次方如果M到10的9次方差距会进一步拉大。OJ的时间限制通常在1秒左右取余版本在极限数据下随时可能超时步进版本则从容得多。复杂度这个指标的用途就在这它不只是一种理论描述更是你选择写法的依据。做题的时候先看一眼数据范围再决定用O(M)还是O(M/N)的算法已经能筛掉一大半新手错误。很多人刷题刷到后面只看算法标签其实数据范围才是第一时间该确认的东西。3.3 防御性编程要不要处理n为0如果题目输入没有保证n非0而你的代码又用了步进写法n0就会无限循环。另外任何数的0倍都是0但0在多数题面里并不算“N的倍数”所以大多数题不会把n设为0。即便如此我还是建议在循环前加一行if (n 0) { return 0; }这不是画蛇添足而是工程习惯。OJ题面写得再清楚也不如自己的代码对异常情况有抵抗力。等以后写真实项目接口传参碰到非法值是很常见的提前养成防御性编程的习惯能少掉很多头发。4. 刷题过程中的常见错误与排查4.1 错误一行尾多一个空格这是初学者最容易被判PE的原因。普通输出 “3 6 9 ” 和 “3 6 9” 在肉眼看来一模一样但判题系统会按字符对比。解决方法就是我前面写的first变量控制法或者用另一种思路先输出第一个数之后每个数前面补空格。两者的本质相同都是把“空格”当成数字之间的分隔符而不是每个数字后面的尾巴。如果你图省事想直接输出“数字空格”然后循环结束前加退格符我也试过能用但看上去很别扭而且有些系统会把这个退格当成字符处理反而报错。最干净的做法就是first变量多三行代码一劳永逸。4.2 错误二死循环导致超时死循环在基础题里很少见但一旦出现就很隐蔽。前面说的n为0是第一种第二种常见于手滑把 i 2 写成 i 2后者变成 i 2每次循环都把i重置循环也永远退不出去。C里 不是合法的自增运算符它等价于先取正号再赋值新手容易漏看。遇到本地跑起来不结束的情况先在循环里加一行 cout i看i的变化规律很快能定位。还有一种情况步进值设成了0。比如 i 0i一直不变。这种情况多发生在变量名写错或者把n赋成了0。用调试输出打印循环变量基本一轮就能看出来。4.3 错误三int溢出如果题目的n和m可以到10的9次方int的32位范围(大约21亿)还算够用但如果倍数超过21亿比如n3000000000或者循环变量一直累加到上亿就要小心。取值达到2^31-1上限后再加1会变成负数循环条件立刻出问题。解决方法是把变量类型改成long long。long long n, m; for (long long i n; i m; i n) { ... }有些同学觉得long long更慢小题用不上。实际上现代CPU对64位整数的运算支持得很好这种级别的性能差异完全可以忽略。宁可每次都用long long也不要赌数据不会超过int范围。我在项目里见过太多线上事故根源就是int溢出代价远大于那一丁点性能。4.4 我的本地对拍调试法这里分享一个我自己一直在用的笨办法写两个版本一个暴力但绝对正确一个优化但可能出错然后用随机数据去对拍。比如取余版当暴力版步进版当优化版生成一万组随机n和m跑完比较输出。如果一万组都一样基本能说明功能正确。对拍脚本用C写也行用Python写也行关键是“随机”和“自动比较”这两步。很多新手只测自己想到的几个用例测过就觉得稳了实际上边界条件覆盖不到。养成对拍习惯之后OJ题的AC率会明显上升这个习惯对后续刷更复杂的题也很有用。我平时会先写一个随机数据生成器再写一个比较脚本。生成器负责产生多组n和m比较脚本负责把两个程序的输出逐行对比。一旦发现不同就把对应输入单独拿出来人工分析。这个过程听起来麻烦但熟练之后一次对拍不超过两分钟却能省下反复提交的等待时间。4.5 提交前最后三查提交之前我会固定做三件事检查题号选对没有检查输入变量顺序有没有搞反检查输出格式里的空格和换行。听起来简单但真的救过我很多次。变量顺序搞反是重灾区比如题面先给M再给N代码里却先读N后读M逻辑全对答案全错。题面、样例、代码三样东西放一起核对比闷头改bug高效得多。5. 从“N的倍数”延伸开去的思考5.1 OJ题与真实工程的差异很多人会问刷这种基础题到底有什么用实话实说这题本身的算法含量不高但它训练的核心能力是“把需求翻译成代码”。这种翻译能力在真实工程里同样重要产品说“这个列表里符合条件的数据要展示”你脑子里立刻能浮现出遍历、判断、收集、输出的过程。语言会换框架会换但这种对流程的把握不会过时。另一方面OJ题和真实工程也有明显差异。工程里要考虑代码的可读性、可维护性和异常处理而OJ题只需要在限定数据下跑出正确结果。所以刷题时不用过度设计但至少要规范输入输出、注意类型边界。这两者的平衡点就是在基础题里用工程化的习惯写小代码。5.2 可以自己加的变体练习如果你想把这道题吃透我建议做几个小变体思路类似但难度递增输出1到M之间所有同时是N和K的倍数输出前K个N的倍数倒序输出M到1之间N的倍数输出小于M且与N互素的数。第一个变体本质上是在求最小公倍数第二个变体只需要控制输出计数第三个变体把循环倒过来写第四个变体用到更细的数学判断。每一个都能在原有代码上小改几步却能帮你把循环和条件判断练得更扎实。我第一次做这题的时候还傻傻地开了个大数组保存倍数再输出后来发现直接边算边输出就行。这里也建议大家学会用简单方式解决简单问题。如果你在东华OJ刷到这一题希望这篇文章能帮你少走几步弯路——别去背题解把代码一行行敲进编辑器跑一遍边界用例再想想每个变量为什么这么写你会有完全不一样的收获。祝AC顺利。