Truy vấn ước bội - MarisaOJ: Marisa Online Judge

Truy vấn ước bội

Time limit: 1000 ms
Memory limit: 512 MB
Cho mảng $A$ gồm $n$ phần tử nguyên và $q$ truy vấn dạng $(l, r, x)$, đếm số lượng số là bội hoặc ước của $x$ trong đoạn $[l,r]$ của mảng $A$. ### Input - Dòng đầu tiên gồm hai số nguyên $n,q$. - Dòng thứ hai gồm $n$ số nguyên $A_i$. - $q$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $l,r,x$ là một truy vấn. ### Output - Với mỗi truy vấn in ra một số nguyên là đáp án. ### Điều kiện - $1 \le n,q \le 10^5$. - $1 \le A_i,x \le 2 \times 10^5$. - $1 \le l \le r \le n$ ### Ví dụ Input: ``` 8 5 12 10 3 18 6 72 28 42 1 8 6 3 7 7 2 6 9 1 5 5 4 8 4 ``` Output: ``` 6 1 3 1 2 ```