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