前陣子在技術群裡看到一道題目:求 1000 以內所有能被 3 或 5 整除的數字之和。第一種解法大家大概都想得到,真正有意思的是第二種——一開始看著有點摸不著頭緒,細想之後再被人點了一下,頓時豁然開朗。

最普遍的做法就是把 1000 以內的數字逐一走過一輪,遇到能被 3 整除或能被 5 整除的就累加起來,迴圈結束後自然就得到總和。思路直白、可讀性高,缺點是要跑完將近一千次判斷。
讓我產生興趣的是第二種解法,它巧妙地借用了數學上的等差數列。一個公差為 d 的等差數列,前 n 項之和為:

解法二的起手式是 (a1+an)/3*3,等價於寫成 3*(1+333)*333/2。這一步做的事,是一次把「所有能被 3 整除的項」加完:首項是 3、末項是 999、項數是 333,套進等差求和公式即可。
同理,sum(Math.floor(input-1)/5))*5 這一段,則是把 1000 以內所有能被 5 整除的項一次加完。
關鍵的最後一筆在這裡:能被 3 整除與能被 5 整除的兩批數字裡,有一群數字被算了兩次,也就是 15 的倍數(15、30、45……)。因此只要再把這批重複的數字減掉一次,就能得到 1000 以內能被 3 或 5 整除的數字總和——本質上就是一句簡單的容斥原理。
兩種寫法對比之後可以發現:暴力遍歷的思維負擔小,公式法則把時間複雜度壓到常數級,差別在你知道自己能用數學把迴圈收掉。這類題目真正的價值,大概就在提醒我們別急著寫迴圈。