Calculate the sum $$ \sum_{i=1}^n \sum_{j=1}^n a_i \mod a_j $$ for some integer $a_i \in \mathbb{Z}.$ If we calculated the usual sum $$ \sum_{i=1}^n \sum_{j=1}^n a_i a_j $$ then it would be easy since $$ \sum_{i=1}^n \sum_{j=1}^n a_i a_j=\left(\sum_{j=1}^n a_i \right)^2$$ and we have the complexity $O(n).$ Unfortunatelly $$ \sum_{i=1}^n \sum_{j=1}^n a_i \mod a_j \neq \sum_{i=1}^n \left(\left(\sum_{j=1}^n a_i \right) \mod a_j \right).$$
Question. Is there an algorithm better then $O(n^2)$ for calculating the sum?