這題預期的解法是利用 meet-in-the-middle 來達到 $\color{black}{O(\sqrt{N})}$ 的時間複雜度。設 $\color{black}{n = \lfloor\sqrt{N}\rfloor}$，將 $\color{black}{S := \sum_{i=1}^N(N\operatorname{mod}i)}$ 的計算拆成前 $\color{black}{n}$ 項的和 $\color{black}{S_1}$ 與後 $\color{black}{N-n}$ 項的和 $\color{black}{S_2}$。如果我們能在 $\color{black}{O(\sqrt{N})}$ 時間內算出 $\color{black}{S_1}$ 與 $\color{black}{S_2}$，就能在相同的時間內算出 $\color{black}{S}$。

由於 $\color{black}{S_1}$ 只有 $\color{black}{n = O(\sqrt{N})}$ 項，本來就能在 $\color{black}{O(\sqrt{N})}$ 時間內算出。$\color{black}{S_2}$ 的部分，若將 $\color{black}{N}$ 除以 $\color{black}{i}$ 寫為 $\color{black}{N = qi+r}$，其中 $\color{black}{r < i}$，則因 $\color{black}{i\ge n+1>\sqrt{N}}$，我們有 $\color{black}{q\le\lfloor\frac N{\sqrt{N}}\rfloor = n}$，且 $\color{black}{r}$ 在 $\color{black}{q}$ 相等的 $\color{black}{i}$ 區間內，形成了公差恰為 $\color{black}{-q}$ 的等差數列（讀者可以試著輸出並觀察 $\color{black}{N = 50}$ 時 $\color{black}{N\operatorname{mod}i}$ 的值是怎麼隨著 $\color{black}{i}$ 遞增而變化的）。由於 $\color{black}{S_2}$ 由 $\color{black}{q = O(\sqrt{N})}$ 個等差數列組成，而每個等差數列的和又可以在 $\color{black}{O(1)}$ 時間內算出，我們發現 $\color{black}{S_2}$ 可以在 $\color{black}{O(\sqrt{N})}$ 時間內算出。