🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Mùa nước nổi, thầy Sơn cùng bà con trong xóm ở Hồng Ngự gom lục bình về phơi khô để đan giỏ bán cho khách du lịch. Trước sân nhà thầy có ~N~ bó lục bình đã phơi, bó thứ ~i~ có đúng ~a_i~ sợi.

Để đan một chiếc giỏ, thầy Sơn chọn hai bó khác nhau ~i~ và ~j~ ~(i < j)~ rồi chia toàn bộ sợi của hai bó thành các lọn, sao cho:

• mỗi lọn chỉ gồm sợi lấy từ cùng một bó,
• mọi lọn có số sợi bằng nhau và không bó nào còn thừa sợi,
• mỗi lọn có số sợi nhiều nhất có thể.

Số sợi của mỗi lọn khi đó được gọi là độ dày của cặp bó ~(i, j)~. Ví dụ hai bó có ~6~ và ~9~ sợi thì mỗi lọn có ~3~ sợi (bó đầu thành ~2~ lọn, bó sau thành ~3~ lọn), độ dày là ~3~.

Mỗi đơn hàng của khách yêu cầu giỏ có độ dày nằm trong một khoảng cho trước. Thầy Sơn nhận ~Q~ đơn hàng, đơn thứ ~k~ cho hai số ~L_k, R_k~. Với mỗi đơn, hãy giúp thầy Sơn đếm xem có bao nhiêu cặp bó ~(i, j)~ với ~1 \le i < j \le N~ có độ dày nằm trong đoạn ~[L_k, R_k]~. Các đơn hàng độc lập với nhau (thầy chỉ đếm, không dùng hết lục bình).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N \le 3 \times 10^5,~ ~1 \le Q \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ ~(1 \le a_i \le 10^6)~.
• ~Q~ dòng tiếp theo, dòng thứ ~k~ chứa hai số nguyên ~L_k, R_k~ ~(1 \le L_k \le R_k \le 10^6)~.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~k~ là số cặp bó có độ dày thuộc đoạn ~[L_k, R_k]~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 2000~.
• Subtask 2 (~30\%~ số điểm): ~a_i \le 3000~ với mọi ~i~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

5 3
6 4 9 10 15
2 3
3 1000000
4 10

Sample Output 1

6
4
1

Giải thích

Có ~10~ cặp bó. Độ dày của từng cặp (ghi theo số sợi của hai bó):

• ~(6, 4) \to 2~; ~(6, 9) \to 3~; ~(6, 10) \to 2~; ~(6, 15) \to 3~;
• ~(4, 9) \to 1~; ~(4, 10) \to 2~; ~(4, 15) \to 1~;
• ~(9, 10) \to 1~; ~(9, 15) \to 3~;
• ~(10, 15) \to 5~.

Đơn ~[2, 3]~ có ~6~ cặp: ~(6, 4), (6, 9), (6, 10), (6, 15), (4, 10), (9, 15)~. Đơn ~[3, 10^6]~ có ~4~ cặp: ~(6, 9), (6, 15), (9, 15), (10, 15)~. Đơn ~[4, 10]~ chỉ có cặp ~(10, 15)~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).