trang chủ / đề bài / icpc24_mb_e

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í {i,j} phân biệt (1≤i≤j≤|Σ|) sao cho số tạo bởi các chữ số của Σ từ vị trí i đến vị trí j (tính cả hai đầu) chia hết cho số nguyên tố ℙ.

Ví dụ, hệ số chia hết của xâu Σ=101010 ứng với ℙ=5 là 12. Các cặp {i,j} và xâu con tương ứng là: {1,2}:10, {1,4}:1010, {1,6}:101010, {2,2}:0, {2,4}:010≡10, {2,6}:01010≡1010, {3,4}:10, {3,6}:1010≡10, {4,4}:0, {4,6}:010≡10, {5,6}:10 và {6,6}:0. Lưu ý một số có các chữ số 0 ở đầu được coi là bằng số tương ứng sau khi bỏ các chữ số 0 đó.

Yêu cầu: Cho xâu chữ số S và số nguyên tố ℙ, hãy trả lời Q truy vấn dạng: tìm hệ số chia hết của xâu con của S từ vị trí l đến vị trí r (tính cả hai đầu).

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên tố ℙ (ℙ≤109+7).
  • Dòng thứ hai chứa xâu chữ số khác rỗng S (|S|≤105).
  • Dòng thứ ba chứa số nguyên dương Q: số truy vấn (Q≤105).
  • Mỗi dòng trong Q dòng tiếp theo mô tả một truy vấn gồm hai số nguyên l và r: biên trái và biên phải của xâu con cần tính hệ số chia hết (1≤l≤r≤|S|).

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ố, ℙ≤109+7
  • 1≤|S|≤105, 1≤Q≤105
  • 1≤l≤r≤|S|

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 [1,6] 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 [1,4], các xâu con chia hết cho 3 là 12, 120, 1203, 0, 03, 3.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0