Lời giải

Xét từng cặp là bất khả thi. Hãy đổi thứ tự lấy tổng sang các ước: một số ~d~ được cộng vào ~f(i, j)~ đúng khi ~d~ là ước của cả ~i~ và ~j~. Vậy

~S = \sum_{d=1}^{n} d \cdot \#\{(i, j) : i \le j \le n,\; d \mid i,\; d \mid j\}~

Trong đoạn ~[1, n]~ có ~m = \left\lfloor n/d \right\rfloor~ bội của ~d~, và số cặp ~i \le j~ lấy từ ~m~ bội đó là ~\dfrac{m(m+1)}{2}~. Do đó

~S = \sum_{d=1}^{n} d \cdot \dfrac{m(m+1)}{2}, \quad m = \left\lfloor n/d \right\rfloor~

Giá trị ~\left\lfloor n/d \right\rfloor~ chỉ nhận khoảng ~2\sqrt{n}~ giá trị khác nhau, nên hãy nhóm các ~d~ có cùng ~\left\lfloor n/d \right\rfloor~ thành từng khối và tính tổng ~d~ trên mỗi khối bằng công thức cấp số cộng.

Cẩn thận: tổng ~d~ trên một khối có thể lên tới ~10^{28}~, vượt xa số nguyên 64 bit — hãy lấy dư trước khi nhân, và dùng nghịch đảo của ~2~ thay cho phép chia.