Ta gọi $g_i$ là hệ số của số nguyên $i$, với hệ số $g_i$ được tính như sau:

• $g_1 = 1$.
• $g_i = i - \Sigma{g_d}$ với mọi $d$ là ước khác $i$ của $i$ (lấy $i$ trừ tổng các giá trị $g_d$)

Đến đây ta chỉ cần tính tổng các giá trị $[\frac{n}{i}] \times [\frac{m}{i}] \times g_i$ (cộng hệ số $g_i$ với mỗi cặp số nguyên có ước chung lớn nhất chia hết cho $i$) với mỗi số nguyên $1 \le i \le \min(n, m)$.

Với cách tính theo hệ số $g$ như thế này, ta giả sử một cặp số $(i, j)$ có ước chung lớn nhất là $d$. Do đó, với cặp $(i, j)$, ta đả cộng vào câu trả lời một lượng bằng tổng các giá trị $g_k$ với $k$ là ước của $d$, do đó hệ số $g_d$ phải bằng $d$ trừ đi tổng các giá trị $g_k$.

Nếu tính theo một cách đơn giản như thế này ta có thể cài đến subtask 2 với độ phức tạp $O(n \sqrt{n})$. Để ăn được subtask 3, các bạn phải dùng đến sàng ước với độ phức tạp $O(n \times \log_2(n))$.