#1085. GCD - Truy vấn GCD

Thắng thích làm những bài toán liên quan đến truy vấn với các con số. Một hôm Thắng tìm được một bài toán mới mà anh ta cho rằng khá khó để giải quyết. Do đó, anh ta nhờ bạn giúp! Cho một dãy số nguyên và truy vấn . Có loại truy vấn sau:

• : Gán ( là số nguyên);
• : Đếm các chỉ số sao cho và ( là các số nguyên). Kí hiệu là ước chung lớn nhất của và . Hãy đưa ra câu trả lời cho mỗi truy vấn loại .

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên là số phần tử của dãy.
• Dòng thứ hai chứa số nguyên .
• Dòng thứ ba chứa số nguyên là số truy vấn.
• Mỗi dòng trong dòng tiếp theo chứa một truy vấn thuộc dạng như mô tả ở trên.

Dữ liệu ra:

• Với mỗi truy vấn loại , ghi ra trên một dòng chứa một số nguyên là câu trả lời của truy vấn đó.

Ví dụ:

Dữ liệu vào:

4
2 3 4 5
3
2 1 4 2
1 2 6
2 1 4 2

Dữ liệu ra:

2
1

Giải thích:

• Với truy vấn đầu tiên: , do đó câu trả lời là .
• Với truy vấn thứ ba: chỉ có , do đó câu trả lời là .

Giới hạn:

• Có số test có ;
• Có số test khác chỉ gồm các truy vấn loại ;
• Có test còn lại: Như ràng buộc trong đề bài.