🎓 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

Dọc bờ kênh xáng trước trường, xã cắm một hàng cọc tiêu rất dài, các cọc được đánh số lần lượt ~1, 2, 3, \dots~ (coi như hàng cọc dài vô tận). Nhân dịp làm công trình thanh niên, thầy Sơn chia học trò thành ba nhóm, mỗi nhóm cầm một màu sơn:

• Nhóm Đỏ sơn mọi cọc có số thứ tự chia hết cho ~a~;
• Nhóm Vàng sơn mọi cọc có số thứ tự chia hết cho ~b~;
• Nhóm Xanh sơn mọi cọc có số thứ tự chia hết cho ~c~.

Một cọc được đúng một nhóm sơn thì có màu tươi, rất đẹp. Một cọc bị từ hai nhóm trở lên sơn chồng lên nhau thì màu bị lem, phải cạo ra sơn lại; còn cọc không nhóm nào sơn thì vẫn giữ màu xi măng.

Thầy Sơn muốn chụp ảnh các đoạn bờ kênh để làm kỷ yếu, nên thầy hỏi ~Q~ câu: với đoạn từ cọc số ~L~ đến cọc số ~R~ (tính cả hai đầu), có bao nhiêu cọc màu tươi (được đúng một nhóm sơn)?

Hãy giúp thầy Sơn trả lời tất cả các câu hỏi.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~a, b, c~ ~(1 \le a, b, c \le 10^{18})~. Ba số này có thể bằng nhau.
• Dòng thứ hai chứa số nguyên ~Q~ ~(1 \le Q \le 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ ~(1 \le L \le R \le 10^{18})~ mô tả một câu hỏi.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~i~ là số cọc màu tươi trong đoạn của câu hỏi thứ ~i~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~Q \le 10~ và ~R \le 10^6~ ở mọi câu hỏi.
• Subtask 2 (~30\%~ số điểm): ~R \le 10^6~ ở mọi câu hỏ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

2 3 5
2
1 10
11 29

Sample Output 1

6
8

Giải thích

Câu hỏi 1, đoạn cọc ~1 \dots 10~: các cọc màu tươi là ~2, 3, 4, 5, 8, 9~; cọc ~6~ và cọc ~10~ bị lem, cọc ~1~ và cọc ~7~ không nhóm nào sơn. Vậy có ~6~ cọc màu tươi.

Câu hỏi 2, đoạn cọc ~11 \dots 29~: các cọc màu tươi là ~14, 16, 21, 22, 25, 26, 27, 28~, tức là ~8~ cọc.

Sample Input 2

9 9 6
1
2 17

Sample Output 2

2

Giải thích

Cọc ~9~ được cả nhóm Đỏ và nhóm Vàng sơn nên bị lem. Trong đoạn từ cọc ~2~ đến cọc ~17~ chỉ có cọc ~6~ và cọc ~12~ là màu tươi.

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