最近又把東華OJ的基礎(chǔ)題翻出來刷了一遍做到第64題“N的倍數(shù)”用C提交的時(shí)候踩了幾個(gè)坑所以把這題的完整思路和代碼實(shí)現(xiàn)整理出來。這道題在入門題里很有代表性循環(huán)、取模、輸入輸出格式三個(gè)基本點(diǎn)全練到了。如果你剛開始刷OJ或者C剛學(xué)完for循環(huán)這一篇可以直接當(dāng)模板用。老實(shí)說這類題的算法難度幾乎為零真正讓新手翻車的往往不是“不會(huì)做”而是“不知道題目要什么”和“輸出格式不對(duì)”。這篇我會(huì)從最常見的版本講起把代碼怎么寫、為什么這樣寫、哪些地方容易摔跤一次說清楚。1. 題目解析與整體思路1.1 題目的常見版本與核心要求“N的倍數(shù)”在東華OJ基礎(chǔ)題里出現(xiàn)過不止一個(gè)版本我見過的至少有兩種。第一種輸入一個(gè)整數(shù)N再輸入一串整數(shù)輸出其中能被N整除的數(shù)第二種輸入整數(shù)N和M輸出1到M之間所有N的倍數(shù)。兩者本質(zhì)是同一個(gè)模型給一個(gè)范圍從中篩出符合條件的數(shù)。這篇以第二種作為主版本因?yàn)樗妮斎胼敵鎏茁犯?jīng)典也更適合拿來練循環(huán)。不管哪個(gè)版本核心動(dòng)作都一樣——先讀數(shù)據(jù)再逐個(gè)判斷最后按格式輸出。對(duì)入門選手來說難的地方不是判斷本身而是你能不能準(zhǔn)確模擬出“逐個(gè)判斷”這個(gè)過程。很多人上來就想用數(shù)學(xué)公式一把梭反而把簡(jiǎn)單題想復(fù)雜了。多數(shù)情況下老老實(shí)實(shí)for循環(huán)就是最優(yōu)解。題目里還會(huì)隱含一些邊界約定比如“倍數(shù)”包不包括0。在數(shù)論里0是任何非零整數(shù)的倍數(shù)但多數(shù)基礎(chǔ)題默認(rèn)討論的是正整數(shù)范圍內(nèi)的倍數(shù)所以1到M這個(gè)區(qū)間里的N的倍數(shù)通常從N本身開始。如果你做題時(shí)發(fā)現(xiàn)樣例輸出里出現(xiàn)了0那就要反過來把0考慮進(jìn)去。這種細(xì)節(jié)全靠讀題時(shí)留意不能想當(dāng)然。1.2 取模運(yùn)算判斷倍數(shù)的唯一標(biāo)準(zhǔn)判斷一個(gè)數(shù)x是不是N的倍數(shù)唯一的依據(jù)就是 x % N 0。%是C的取余運(yùn)算符它返回兩個(gè)整數(shù)相除的余數(shù)。如果余數(shù)是0說明x能被N整除也就是x是N的倍數(shù)。如果余數(shù)不是0說明除不凈。用一個(gè)生活化的例子一箱蘋果按10個(gè)一袋打包剩下幾個(gè)只能散裝散裝的個(gè)數(shù)就是余數(shù)散裝個(gè)數(shù)為0說明剛好裝完。拿具體數(shù)字走一遍N3時(shí)9 % 3 09是3的倍數(shù)7 % 3 17不是3的倍數(shù)。N5時(shí)10 % 5 010是5的倍數(shù)12 % 5 212不是5的倍數(shù)。理解到這個(gè)層面代碼的核心判斷其實(shí)已經(jīng)寫完了剩下的問題只有兩個(gè)循環(huán)從哪開始、到哪結(jié)束以及輸出怎么處理。另外要注意取余運(yùn)算在C里對(duì)負(fù)數(shù)的處理規(guī)則和數(shù)學(xué)上不太一樣。比如 -3 % 2數(shù)學(xué)上余數(shù)可以是1但C給出的結(jié)果是-1。判斷“是否為倍數(shù)”時(shí)直接用 x % N 0 其實(shí)不受影響因?yàn)槟鼙徽龝r(shí)余數(shù)一定是0但如果你寫的是 x % N 1遇到負(fù)數(shù)就可能翻車?；A(chǔ)題一般不涉及負(fù)數(shù)但心里有數(shù)總沒壞處。1.3 復(fù)雜度分析和寫法選擇如果選“遍歷1到M逐個(gè)取余”的方案時(shí)間復(fù)雜度是O(M)M是多少就循環(huán)多少次。M等于10的4次方、10的5次方時(shí)完全沒問題但一旦M到10的9次方量級(jí)循環(huán)次數(shù)會(huì)非常嚇人。這時(shí)候更聰明的辦法是步進(jìn)法倍數(shù)本身是等差增長(zhǎng)的直接從N開始每次加N這樣循環(huán)次數(shù)直接降到M/N。兩種方案一種思路直觀一種效率更高。我不建議一上來就追求效率先保證寫對(duì)再考慮優(yōu)化。初學(xué)階段用取余方案理解題意熟練之后換成步進(jìn)方案不僅能AC還能慢慢培養(yǎng)“用數(shù)學(xué)視角簡(jiǎn)化循環(huán)”的意識(shí)。這個(gè)意識(shí)的養(yǎng)成比單純過一道入門題重要得多。2. 完整代碼實(shí)現(xiàn)與逐行解讀2.1 最推薦的基礎(chǔ)版本我先把最直接的代碼貼出來后面再逐段解釋。#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然后用一個(gè)for循環(huán)從1遍歷到m。在循環(huán)體內(nèi)部判斷i是否能被n整除能就輸出。first變量用來控制空格第一個(gè)輸出的數(shù)前面不放空格后面的每個(gè)數(shù)前面補(bǔ)一個(gè)空格這樣就不會(huì)出現(xiàn)行尾多余空格的問題。輸出格式在OJ上是很嚴(yán)肅的事情。有些判題系統(tǒng)只看數(shù)字多個(gè)空格不報(bào)錯(cuò)但有些系統(tǒng)會(huì)報(bào)Presentation Error也就是“答案對(duì)但格式不對(duì)”。用first變量控制空格成本很低卻能避免一次無謂的返工。很多新手覺得無所謂等被PE教育一次就記住了。2.2 步進(jìn)倍增寫法與效率對(duì)比如果你已經(jīng)能流暢寫上面的版本我建議看一眼下面這個(gè)寫法#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; }區(qū)別只在一行循環(huán)初始值從1改成n循環(huán)步長(zhǎng)從i改成i n。這樣每一次循環(huán)拿到的都是n的倍數(shù)連if判斷都省了。同樣輸出1到100之間的所有7的倍數(shù)第一種寫法要循環(huán)100次第二種只有14次。數(shù)據(jù)小的時(shí)候看不出差別數(shù)據(jù)上億的時(shí)候這是天壤之別。但這寫法有個(gè)致命前提n不能是0。如果n是0i n永遠(yuǎn)不改變i的值循環(huán)會(huì)一直轉(zhuǎn)下去直接超時(shí)。所以要么題目明確保證n為正整數(shù)要么自己加個(gè)防御判斷。這個(gè)坑我后面會(huì)細(xì)講。如果你擔(dān)心n是負(fù)數(shù)可以在循環(huán)前加一行 i abs(n)或者干脆把題目范圍限定在正整數(shù)。大多數(shù)OJ題不會(huì)故意用負(fù)數(shù)卡人但有些綜合題會(huì)混著來保持警惕就好。2.3 多組輸入的兼容寫法東華OJ的入門題大多是一次輸入一組數(shù)據(jù)但也有幾道題會(huì)隱藏多組數(shù)據(jù)要求讀到文件末尾才結(jié)束。這類題用while循環(huán)包一層就行#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的判斷條件當(dāng)不再有數(shù)據(jù)可讀時(shí)cin會(huì)進(jìn)入失敗狀態(tài)循環(huán)自然結(jié)束。這樣一組一組處理每組之間用換行隔開能兼容單組和多組兩種情況。你可能會(huì)想多寫這個(gè)while會(huì)不會(huì)影響性能不會(huì)文件輸入本身是分塊的cin緩沖已經(jīng)做了優(yōu)化。對(duì)入門題來說這種寫法是安全的。2.4 用scanf還是cin最近網(wǎng)上關(guān)于C快讀的討論很多有人一說scanf就激動(dòng)好像cin無論如何都會(huì)超時(shí)。其實(shí)對(duì)于這道題cin和scanf都能輕松跑過。cin的優(yōu)勢(shì)是類型安全、代碼簡(jiǎn)潔缺點(diǎn)是默認(rèn)要兼容C的stdio會(huì)多一層同步操作。如果你實(shí)在不放心可以在main開頭加一行ios::sync_with_stdio(false); cin.tie(0);這行代碼關(guān)掉cin與stdio的同步之后cin的輸入速度會(huì)明顯提升。需要提醒的是一旦用了這個(gè)就不要再混用scanf和cin讀同一個(gè)流否則可能出現(xiàn)數(shù)據(jù)錯(cuò)亂。這道題完全用cin就夠不用折騰scanf。等以后刷到千萬級(jí)輸入量的題再認(rèn)真研究快讀也不遲。3. 邊界條件與現(xiàn)場(chǎng)測(cè)試3.1 特殊輸入對(duì)應(yīng)的預(yù)期輸出寫代碼是一回事能不能在各種刁鉆數(shù)據(jù)下存活是另一回事。我整理了幾個(gè)典型的邊界用例建議你本地跑一遍輸入預(yù)期輸出說明3 103 6 9常規(guī)情況1 51 2 3 4 51是所有數(shù)的倍數(shù)5 4空行范圍內(nèi)沒有倍數(shù)100 200100 200N和M同量級(jí)-3 103 6 9負(fù)數(shù)N需要取絕對(duì)值后處理負(fù)數(shù)的情況要特別小心。C里 -3 % 3 的結(jié)果是0說明取模對(duì)負(fù)數(shù)也成立但 -3 % 2 的結(jié)果是-1而不是1如果你直接用 i % n 0 判斷負(fù)數(shù)不影響的場(chǎng)景其實(shí)還好。關(guān)鍵是步進(jìn)寫法里 n 為負(fù)數(shù)時(shí)i n 會(huì)往小走循環(huán)永遠(yuǎn)跑不到m。穩(wěn)妥做法是循環(huán)前先取絕對(duì)值或直接判斷 n 0 就返回。3.2 大范圍數(shù)據(jù)下的性能實(shí)測(cè)我在本機(jī)模擬了M 10^8、N 7的規(guī)模分別跑取余版本和步進(jìn)版本結(jié)果是取余版本跑了接近1秒步進(jìn)版本只用了不到0.1秒差了十倍。這還只是10的8次方如果M到10的9次方差距會(huì)進(jìn)一步拉大。OJ的時(shí)間限制通常在1秒左右取余版本在極限數(shù)據(jù)下隨時(shí)可能超時(shí)步進(jìn)版本則從容得多。復(fù)雜度這個(gè)指標(biāo)的用途就在這它不只是一種理論描述更是你選擇寫法的依據(jù)。做題的時(shí)候先看一眼數(shù)據(jù)范圍再?zèng)Q定用O(M)還是O(M/N)的算法已經(jīng)能篩掉一大半新手錯(cuò)誤。很多人刷題刷到后面只看算法標(biāo)簽其實(shí)數(shù)據(jù)范圍才是第一時(shí)間該確認(rèn)的東西。3.3 防御性編程要不要處理n為0如果題目輸入沒有保證n非0而你的代碼又用了步進(jìn)寫法n0就會(huì)無限循環(huán)。另外任何數(shù)的0倍都是0但0在多數(shù)題面里并不算“N的倍數(shù)”所以大多數(shù)題不會(huì)把n設(shè)為0。即便如此我還是建議在循環(huán)前加一行if (n 0) { return 0; }這不是畫蛇添足而是工程習(xí)慣。OJ題面寫得再清楚也不如自己的代碼對(duì)異常情況有抵抗力。等以后寫真實(shí)項(xiàng)目接口傳參碰到非法值是很常見的提前養(yǎng)成防御性編程的習(xí)慣能少掉很多頭發(fā)。4. 刷題過程中的常見錯(cuò)誤與排查4.1 錯(cuò)誤一行尾多一個(gè)空格這是初學(xué)者最容易被判PE的原因。普通輸出 “3 6 9 ” 和 “3 6 9” 在肉眼看來一模一樣但判題系統(tǒng)會(huì)按字符對(duì)比。解決方法就是我前面寫的first變量控制法或者用另一種思路先輸出第一個(gè)數(shù)之后每個(gè)數(shù)前面補(bǔ)空格。兩者的本質(zhì)相同都是把“空格”當(dāng)成數(shù)字之間的分隔符而不是每個(gè)數(shù)字后面的尾巴。如果你圖省事想直接輸出“數(shù)字空格”然后循環(huán)結(jié)束前加退格符我也試過能用但看上去很別扭而且有些系統(tǒng)會(huì)把這個(gè)退格當(dāng)成字符處理反而報(bào)錯(cuò)。最干凈的做法就是first變量多三行代碼一勞永逸。4.2 錯(cuò)誤二死循環(huán)導(dǎo)致超時(shí)死循環(huán)在基礎(chǔ)題里很少見但一旦出現(xiàn)就很隱蔽。前面說的n為0是第一種第二種常見于手滑把 i 2 寫成 i 2后者變成 i 2每次循環(huán)都把i重置循環(huán)也永遠(yuǎn)退不出去。C里 不是合法的自增運(yùn)算符它等價(jià)于先取正號(hào)再賦值新手容易漏看。遇到本地跑起來不結(jié)束的情況先在循環(huán)里加一行 cout i看i的變化規(guī)律很快能定位。還有一種情況步進(jìn)值設(shè)成了0。比如 i 0i一直不變。這種情況多發(fā)生在變量名寫錯(cuò)或者把n賦成了0。用調(diào)試輸出打印循環(huán)變量基本一輪就能看出來。4.3 錯(cuò)誤三int溢出如果題目的n和m可以到10的9次方int的32位范圍(大約21億)還算夠用但如果倍數(shù)超過21億比如n3000000000或者循環(huán)變量一直累加到上億就要小心。取值達(dá)到2^31-1上限后再加1會(huì)變成負(fù)數(shù)循環(huán)條件立刻出問題。解決方法是把變量類型改成long long。long long n, m; for (long long i n; i m; i n) { ... }有些同學(xué)覺得long long更慢小題用不上。實(shí)際上現(xiàn)代CPU對(duì)64位整數(shù)的運(yùn)算支持得很好這種級(jí)別的性能差異完全可以忽略。寧可每次都用long long也不要賭數(shù)據(jù)不會(huì)超過int范圍。我在項(xiàng)目里見過太多線上事故根源就是int溢出代價(jià)遠(yuǎn)大于那一丁點(diǎn)性能。4.4 我的本地對(duì)拍調(diào)試法這里分享一個(gè)我自己一直在用的笨辦法寫兩個(gè)版本一個(gè)暴力但絕對(duì)正確一個(gè)優(yōu)化但可能出錯(cuò)然后用隨機(jī)數(shù)據(jù)去對(duì)拍。比如取余版當(dāng)暴力版步進(jìn)版當(dāng)優(yōu)化版生成一萬組隨機(jī)n和m跑完比較輸出。如果一萬組都一樣基本能說明功能正確。對(duì)拍腳本用C寫也行用Python寫也行關(guān)鍵是“隨機(jī)”和“自動(dòng)比較”這兩步。很多新手只測(cè)自己想到的幾個(gè)用例測(cè)過就覺得穩(wěn)了實(shí)際上邊界條件覆蓋不到。養(yǎng)成對(duì)拍習(xí)慣之后OJ題的AC率會(huì)明顯上升這個(gè)習(xí)慣對(duì)后續(xù)刷更復(fù)雜的題也很有用。我平時(shí)會(huì)先寫一個(gè)隨機(jī)數(shù)據(jù)生成器再寫一個(gè)比較腳本。生成器負(fù)責(zé)產(chǎn)生多組n和m比較腳本負(fù)責(zé)把兩個(gè)程序的輸出逐行對(duì)比。一旦發(fā)現(xiàn)不同就把對(duì)應(yīng)輸入單獨(dú)拿出來人工分析。這個(gè)過程聽起來麻煩但熟練之后一次對(duì)拍不超過兩分鐘卻能省下反復(fù)提交的等待時(shí)間。4.5 提交前最后三查提交之前我會(huì)固定做三件事檢查題號(hào)選對(duì)沒有檢查輸入變量順序有沒有搞反檢查輸出格式里的空格和換行。聽起來簡(jiǎn)單但真的救過我很多次。變量順序搞反是重災(zāi)區(qū)比如題面先給M再給N代碼里卻先讀N后讀M邏輯全對(duì)答案全錯(cuò)。題面、樣例、代碼三樣?xùn)|西放一起核對(duì)比悶頭改bug高效得多。5. 從“N的倍數(shù)”延伸開去的思考5.1 OJ題與真實(shí)工程的差異很多人會(huì)問刷這種基礎(chǔ)題到底有什么用實(shí)話實(shí)說這題本身的算法含量不高但它訓(xùn)練的核心能力是“把需求翻譯成代碼”。這種翻譯能力在真實(shí)工程里同樣重要產(chǎn)品說“這個(gè)列表里符合條件的數(shù)據(jù)要展示”你腦子里立刻能浮現(xiàn)出遍歷、判斷、收集、輸出的過程。語言會(huì)換框架會(huì)換但這種對(duì)流程的把握不會(huì)過時(shí)。另一方面OJ題和真實(shí)工程也有明顯差異。工程里要考慮代碼的可讀性、可維護(hù)性和異常處理而OJ題只需要在限定數(shù)據(jù)下跑出正確結(jié)果。所以刷題時(shí)不用過度設(shè)計(jì)但至少要規(guī)范輸入輸出、注意類型邊界。這兩者的平衡點(diǎn)就是在基礎(chǔ)題里用工程化的習(xí)慣寫小代碼。5.2 可以自己加的變體練習(xí)如果你想把這道題吃透我建議做幾個(gè)小變體思路類似但難度遞增輸出1到M之間所有同時(shí)是N和K的倍數(shù)輸出前K個(gè)N的倍數(shù)倒序輸出M到1之間N的倍數(shù)輸出小于M且與N互素的數(shù)。第一個(gè)變體本質(zhì)上是在求最小公倍數(shù)第二個(gè)變體只需要控制輸出計(jì)數(shù)第三個(gè)變體把循環(huán)倒過來寫第四個(gè)變體用到更細(xì)的數(shù)學(xué)判斷。每一個(gè)都能在原有代碼上小改幾步卻能幫你把循環(huán)和條件判斷練得更扎實(shí)。我第一次做這題的時(shí)候還傻傻地開了個(gè)大數(shù)組保存倍數(shù)再輸出后來發(fā)現(xiàn)直接邊算邊輸出就行。這里也建議大家學(xué)會(huì)用簡(jiǎn)單方式解決簡(jiǎn)單問題。如果你在東華OJ刷到這一題希望這篇文章能幫你少走幾步彎路——?jiǎng)e去背題解把代碼一行行敲進(jìn)編輯器跑一遍邊界用例再想想每個(gè)變量為什么這么寫你會(huì)有完全不一樣的收獲。祝AC順利。