Khác Ước Chung · canuc80k2206 · Thuật toán Canuc80k

Cho một dãy số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ . Với mỗi truy vấn đoạn $[l, r]$ , gọi $g$ là ước chung lớn nhất của tất cả phần tử trong đoạn đó.

Hãy đếm số vị trí $i$ thuộc $[l, r]$ mà $a_{i}$ khác $g$ .

Input

Dòng đầu chứa số nguyên $n$ - số phần tử của dãy.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .
Dòng thứ ba chứa số nguyên $q$ - số truy vấn.
Mỗi dòng trong $q$ dòng tiếp theo chứa hai số nguyên $l$ và $r$ .

Output

Với mỗi truy vấn, in số phần tử khác ước chung lớn nhất của đoạn trên một dòng.

Constraints

$1 \leq n, q \leq 1 0^{5}$ .
$1 \leq a_{i} \leq 1 0^{9}$ .
$1 \leq l \leq r \leq n$ trong mọi truy vấn.
Dãy không thay đổi trong quá trình xử lý.

Scoring

Subtask $1$ ( $50%$ số điểm): $n, q \leq 200$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

7
6 10 15 6 9 3 6
5
1 3
1 4
4 7
1 1
1 7

Output

Giải thích: Trên đoạn $[4, 7]$ , ước chung lớn nhất là $3$ và chỉ phần tử ở vị trí $6$ bằng giá trị này, nên có $3$ phần tử được đếm. Đoạn $[1, 1]$ chỉ chứa chính ước chung lớn nhất của nó nên kết quả bằng $0$ .

Phân tích: Với mỗi đoạn, trước hết cần biết GCD g. Sau đó bài toán chỉ còn là đếm số lần g xuất hiện trong đoạn rồi lấy độ dài đoạn trừ đi số đó.
Thuật toán: Xây Sparse Table GCD trên dãy. Đồng thời, với mỗi giá trị, lưu danh sách tăng dần các vị trí xuất hiện. Một truy vấn lấy g trong O(1), sau đó dùng lower_bound và upper_bound trên danh sách vị trí của g để đếm số lần xuất hiện trong [l,r].
Chứng minh tính đúng đắn: Sparse Table cho đúng GCD của toàn đoạn. Danh sách vị trí của g chứa đúng mọi chỉ số có giá trị bằng g; hiệu của hai phép tìm kiếm nhị phân là chính xác số vị trí như vậy nằm trong truy vấn. Lấy độ dài đoạn trừ đi số lượng này cho đúng số phần tử khác g.
Độ phức tạp: Tiền xử lý tốn O(n log n) thời gian và bộ nhớ. Mỗi truy vấn tốn O(log n).