Truy vấn GCD
Đề bài
Mô tả
Cho mảng gồm số nguyên dương và truy vấn, mỗi truy vấn có dạng . Với mỗi truy vấn, hãy đếm số đoạn con nằm trong phạm vi từ đến có ước chung lớn nhất không vượt quá . Nói cách khác, cần đếm số cặp chỉ số thỏa mãn:
- ;
- .
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (, ).
- Dòng thứ hai chứa số nguyên dương () mô tả mảng.
- dòng tiếp theo, mỗi dòng chứa ba số nguyên (, ) mô tả một truy vấn.
Dữ liệu ra
Với mỗi truy vấn, in ra đáp án trên một dòng.
Ràng buộc
- , .
- .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 5 3 9 6 2 8 4 1 5 3 2 4 3 1 5 4 2 6 2 1 6 1 |
12 4 12 9 6 |
Ở truy vấn thứ hai, các đoạn con trong phạm vi là , , , , , với ước chung lớn nhất lần lượt là ; có giá trị không vượt quá . |
| 5 4 12 18 8 5 10 1 5 1 1 3 5 2 5 6 3 3 8 |
6 2 7 1 |
Ví dụ này không có trong đề gốc. Ở truy vấn thứ hai, các đoạn và có ước chung lớn nhất bằng , các đoạn còn lại có ước chung lớn nhất là . |
Bình luận