Consider the following sum, bounded by limit $L$: $$\sum_{r=1}^L \sum_{i=1}^L \left \lfloor \frac {L}{\left ( \frac {r^2+i^2}{gcd(r,i)} \right )}\right \rfloor \cdot 2r$$ For better readability, define $g=gcd(r,i)$ and further denote $d = \frac {r^2+i^2}{g} $ as $g$ divides $r^2+i^2$. It is not difficult to see we can rearrange the sum so the $2r$ appears in the outter sum. With the new notation, this allows the sum to be written in the following way: $$\sum_{r=1}^L 2 r \sum_{i=1}^L \left \lfloor \frac {L}{d}\right \rfloor$$ I am interested in evaluating this sum. As it currently stands, the computational complexity of this calculation is $O(n^2)$. I know there exists a better algorithm with a better running time analysis, but I can't derive it. I know it because this is a part of an online problem which asks for $L=10^8$. This sum produces the correct results for some smaller sample values given. From computation results, it seems that for $r,i$ $\gt \frac L2$ there is no contribution to the sum, which makes sense, due to the floor function. This reduces the running time but the algorithm is still $O(n^2)$.
I am looking for a way to get the same results but faster. It may be done with a new summation approach, or a pure algorithmic speed-up involving a more sophisticated implementation of this sum. How can I do better than this? I am looking for at least a linear algorithm $O(n)$, otherwise the computation for the limit I am looking for is unfeasible.