Hệ số chia hết
Đề bài
Mô tả
Cho xâu chữ số là một mật mã bí ẩn. Trong dãy này tồn tại một đại lượng bí ẩn gọi là hệ số chia hết, gắn với một số nguyên tố . Hệ số này được định nghĩa là số cặp vị trí phân biệt () sao cho số tạo bởi các chữ số của từ vị trí đến vị trí (tính cả hai đầu) chia hết cho số nguyên tố .
Ví dụ, hệ số chia hết của xâu ứng với là . Các cặp và xâu con tương ứng là: , , , , , , , , , , và . Lưu ý một số có các chữ số ở đầu được coi là bằng số tương ứng sau khi bỏ các chữ số đó.
Yêu cầu: Cho xâu chữ số và số nguyên tố , hãy trả lời truy vấn dạng: tìm hệ số chia hết của xâu con của từ vị trí đến vị trí (tính cả hai đầu).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên tố ().
- Dòng thứ hai chứa xâu chữ số khác rỗng ().
- Dòng thứ ba chứa số nguyên dương : số truy vấn ().
- Mỗi dòng trong dòng tiếp theo mô tả một truy vấn gồm hai số nguyên và : biên trái và biên phải của xâu con cần tính hệ số chia hết ().
Dữ liệu ra
Với mỗi truy vấn, in trên một dòng một số nguyên là hệ số chia hết của xâu con tương ứng.
Ràng buộc
- là số nguyên tố,
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 101010 5 1 1 1 6 2 2 2 4 3 3 |
0 12 1 4 0 |
Ví dụ của đề gốc. Truy vấn chính là ví dụ trong đề bài. |
| 3 1203 4 1 4 2 3 4 4 1 1 |
6 1 1 0 |
Ví dụ bổ sung, tính bằng lời giải mẫu. Với , các xâu con chia hết cho là , , , , , . |
Bình luận