Tổng Bội Chung Nhỏ Nhất Mọi Cặp

Buổi 57 — Sàng & Euler Totient
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho mảng $A$ gồm $N$ số nguyên dương. Hãy tính: \[\sum_{1 \le i < j \le N} \text{lcm}(A_i, A_j) \pmod{10^9 + 7}\]

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($2 \le N \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^5$).
Dữ liệu ra

Một số nguyên duy nhất là kết quả bài toán modulo $10^9 + 7$.

Ví dụ
Input Output
3
2 3 4
22
4
1 2 3 4
31
Giới hạn
  • $2 \le N \le 10^5$
  • $1 \le A_i \le 10^5$
Draft saved