sum of weigted multiplicative function Let $f$ is mulitplicative function, and $N$ is given integer,
then,
$$\sum_{n=1}^N \sum_{l=1}^{n} \lfloor \frac{n}{l} \rfloor f(l) $$
How compute this nicely?
Is there no way to get this with O(N) if $f$ is preprocessed?
 A: We have a double sum, which (if implemented naively) would require $O(N^2)$ integer operations, additionally to the cost of computing the $f$-values. A standard technique in such cases is to change the order of summation. The sum is over all pairs $(n,l)$ satisfying $1\le l\le n\le N$, so we can sum over $n$, first:
$$\sum_{n=1}^N \sum_{l=1}^{n} \lfloor n/l \rfloor f(l)=\sum^N_{l=1}f(l)\sum^N_{n=l}\lfloor n/l \rfloor.$$
Now $\lfloor n/l \rfloor$ is constant between consecutive multiples of $l$, so we have some blocks of $l$ equal values plus some rest of a period where $\lfloor n/l \rfloor=\lfloor N/l \rfloor$, meaning
$$s(N,l)=\sum^N_{n=l}\lfloor n/l \rfloor=l\,\frac{\lfloor N/l \rfloor(\lfloor N/l \rfloor-1)}2+(N \bmod l+1)\,\lfloor N/l \rfloor.$$ Using $N \bmod l=N-l\,\lfloor N/l \rfloor$, we can write this as $$s(N,l)=(N+1)\,\lfloor N/l \rfloor-l\,\frac{\lfloor N/l \rfloor(\lfloor N/l \rfloor+1)}2.$$ Depending on the shape of $f$, the resulting sum $$\sum_{n=1}^N \sum_{l=1}^{n} \lfloor n/l \rfloor f(l)=\sum^N_{l=1}f(l)\,s(N,l)$$ can often be computed still more efficiently, using the fact that $\lfloor N/l \rfloor$ takes only $O(N^{1/2})$ different values.
