Bedan Contest #02 - A - Đếm số chia hết

Điểm: 1300 (thành phần)

Thời gian: 1.5s

Bộ nhớ: 256M

Input: divcnt.inp

Output: divcnt.out

Tác giả:

flo

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python

Đây là bài đầu tiên nên tôi cũng không muốn thêm tình huống hay làm đề bài dài hơn để làm rối bạn hết cả. Vì thế, nội dung bài này tôi viết khá là ngắn gọn, cụ thể là như sau.

Nội dung bài toán

Cho dãy $a$ gồm $n$ phần tử, có $q$ truy vấn cần thực hiện có dạng như sau:

$l$ $r$ $m$ : Đếm số lượng số trong đoạn $[l, r]$ mà $m$ chia hết.

Đấy, tôi đã nói rồi. Đề bài chỉ ngắn gọn thế thôi, chúc bạn may mắn và đừng bị vấn đề kĩ năng nhé.

Input, Output and Scoring

Input (divcnt.inp)

$2$ số nguyên dương $n, q$ $(1 \le n, q \le 2 \times 10^5)$ .
Dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ $(1 \le a_i \le 2 \times 10^5)$ .
$q$ dòng tiếp theo, mỗi dòng là $3$ số nguyên dương $l, r, m$ $(1 \le l \le r \le n; 1 \le m \le 2 \times 10^5)$ .

Output (divcnt.out)

Với mỗi dòng, hãy in ra kết quả thỏa mãn.

Scoring

Subtask $1$ $(20\%)$ : $1 \le n, q \le 2 \times 10^3$ .
Subtask $2$ $(80\%)$ : Không giới hạn gì thêm.

Example

Input

Output

3
2

Note

Trong đoạn $[2, 5]$ , có $3$ số mà $6$ chia hết là $2, 3, 2$ .
Trong đoạn $[1, 3]$ , có $2$ số mà $10$ chia hết là $1, 2$ .

Bình luận

Không có bình luận nào.