Sum of all pairs of GCD.

Question

I would like to calculate sum of $GCD(i, j)$ of all pairs $1 \le i \le n, 1 \le j \le m$, i.e. $\sum_{i=1}^n \sum_{j=1}^m GCD(i, j)$. Is there any faster method than calculating all those $n * m$ gcd's and summing them?

Answer 1

If you have $O(n*m)$ memory, you can store prevous GCD values and calculate GCD with $O(1)$ complexity