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

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