MAXDIV - Đếm đoạn chia hết
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
498M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho số nguyên dương ~k~ và một dãy gồm ~N~ số nguyên dương~a_1, a_2, ..., a_n~. Tìm số cặp số nguyên dương (~l, r~) với ~l~ ≤ ~r~, sao cho trong các số từ ~a_l~ đến ~a_r~, có tối đa một số chia hết cho ~k~.
Input
- Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~k~ (~N~ ≤ ~3*10^5~, ~k ≤ 10^9~).
- Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~(~a_i ≤ 10^9~).
Output
- Một dòng duy nhất gồm số lượng cặp số (~l~, ~r~) thỏa mãn đề bài.
Sample
Input #1
5 2
1 2 3 4 5
Output #1
11
Hint
Giải thích:
- Các cặp số (~l, r~) thỏa mãn là: ~(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,4), (3,5), (4,4), (4,5), (5,5)~.
Ràng buộc:
- Subtask 1 (20% số test): ~N~ ≤ 200
- Subtask 2 (40% số test): ~N~ ≤ 2000
- Subtask 3 (40% số test): Không có ràng buộc gì thêm.
Problem source: Free Contest 120
Bình luận
dùng kĩ thuật: Tìm kiếm nhị phân O(nlogn) hoặc Hai Con Trỏ O(2n) nhé
đề hay quá
đề thật sáng tạo
đề bảo tối đa 1 số chia hết cho k tức là có thể 0 số nào chia hết hoặc chỉ 1 số duy nhất.
cặp (1,1) sao chia hết cho 2 đc
đề giải thích gì kì v