#526. GCDQUERY – Truy vấn ước chung lớn nhất

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho dãy số nguyên dương a_1, a_2, …, a_n q truy vấn, mỗi truy vấn là một cặp số u, v\ (1 ≤ u ≤ v ≤ n) . Bạn cần trả lới UCLN của các số a_u, a_{u + 1}, …, a_v .

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương n q là số phần tử của dãy và số truy vấn;
  • Dòng thứ hai chưa n số nguyên dương a_1, a_2, …, a_n ;
  • q dòng sau, mỗi dòng chứa hai số nguyên u, v .

Hai số liên tiếp trên một dòng cách nhau một khoảng trắng.

Dữ liệu ra:

  • In ra trên một dòng q số nguyên ứng với q truy vấn. Hai số liên tiếp cách nhau một khoảng trắng.

Ví dụ:

Dữ liệu vào:
4 3
3 6 4 8
1 2
1 3
2 4
Dữ liệu ra:
3 1 2 

Giới hạn:

  • 1 ≤ n ≤ 10^5; 1 ≤ q ≤ 10^6; 1≤ a ≤ 10^{12} .