求[sum_{k=1}^N f_k]
显然这玩意是可以(O(N))的，看起来也不能再优化了。
但是在这个宇宙中确实还存在着更快的算法……
令[g_n=sum_{d|n}f_d , F_n=sum_{k=1}^{n}f_k]
因为[sum_{k=1}^N g_k = sum_{k=1}^N {f_k lfloor frac Nk floor} = sum_{k=1}^N F_{lfloor frac Nk floor}]
整理得到[F_N=sum_{k=1}^N g_k - sum_{k=2}^N F_{lfloor frac Nk floor}]
如果能够在 (O(sqrt{N}))的时间内求出(sum_{k=1}^N g_k)，那么可以在(O(N^frac 34))的时间内计算出(F(N))。
(sum_{k=1}^N g_k)对于某些特殊的(g_k)能做的很快，例如[sum_{k=1}^Nsum_{d|k}mu(d)=1][sum_{k=1}^N sum_{d|k}phi(d)=sum_{k=1}^N k=frac{N(N+1)}{2}]
如果(g_n)能够很快的计算，那么可以对于(n leq N^frac 23)线性暴力计算(F_n)，否则递归计算，可以做到(O(N^frac 23))。