trang chủ / đề bài / icpc22_nat_g

Truy vấn GCD

Đề bài

Mô tả

Cho mảng a gồm n số nguyên dương a1,a2,…,an và q truy vấn, mỗi truy vấn có dạng l r d. Với mỗi truy vấn, hãy đếm số đoạn con nằm trong phạm vi từ l đến r có ước chung lớn nhất không vượt quá d. Nói cách khác, cần đếm số cặp chỉ số (u,v) thỏa mãn:

  • l≤u≤v≤r;
  • gcd(au,au+1,…,av−1,av)≤d.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và q (1≤n≤2×105, 1≤q≤2×105).
  • Dòng thứ hai chứa n số nguyên dương a1,a2,…,an (1≤ai≤109) mô tả mảng.
  • q dòng tiếp theo, mỗi dòng chứa ba số nguyên l r d (1≤l≤r≤n, 1≤d≤109) 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

  • 1≤n≤2×105, 1≤q≤2×105.
  • 1≤ai≤109.
  • 1≤l≤r≤n, 1≤d≤109.

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 [2,4] là [9], [6], [2], [9,6], [6,2], [9,6,2] với ước chung lớn nhất lần lượt là 9,6,2,3,2,1; có 4 giá trị không vượt quá 3.
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 [18,8] và [12,18,8] có ước chung lớn nhất bằng 2, các đoạn còn lại có ước chung lớn nhất là 12,18,8,6.

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