최대공약수들의 최댓값

시간 제한1초메모리 제한2048 MB

요약

정수 수열과 여러 구간이 주어질 때, 각 구간 안에서 서로 다른 두 위치의 수를 골라 얻는 최대공약수 중 가장 큰 값을 구합니다.

난이도: 보통10점 중 6점
유형: 정수론, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

정수 수열과 그 수열 위의 구간 여러 개가 주어진다. 구간은 가장 왼쪽 위치와 가장 오른쪽 위치로 지정된다. $k$ 개의 정수로 이루어진 구간에는 서로 다른 위치에 있는 정수 쌍이 $k(k - 1)/2$ 개 있고, 각 쌍마다 최대공약수가 있다. 주어진 각 구간에 대해 이 최대공약수들 중 가장 큰 값을 구하라.

예를 들어 수열이 $(a_1, \dots , a_6) = (10, 20, 30, 40, 50, 60)$ 이고 전체 수열을 구간으로 지정하면, 서로 다른 위치 $x$ 와 $y$ 에 있는 정수 15쌍을 고려한다.

$x$	$1$	$1$	$1$	$1$	$1$	$2$	$2$	$2$	$2$	$3$	$3$	$3$	$4$	$4$	$5$
$y$	$2$	$3$	$4$	$5$	$6$	$3$	$4$	$5$	$6$	$4$	$5$	$6$	$5$	$6$	$6$
$a_x$	$10$	$10$	$10$	$10$	$10$	$20$	$20$	$20$	$20$	$30$	$30$	$30$	$40$	$40$	$50$
$a_y$	$20$	$30$	$40$	$50$	$60$	$30$	$40$	$50$	$60$	$40$	$50$	$60$	$50$	$60$	$60$
$\gcd(a_x,a_y)$	$10$	$10$	$10$	$10$	$10$	$10$	$20$	$10$	$20$	$10$	$10$	$30$	$10$	$20$	$10$

이 15쌍의 최대공약수 중 최댓값은 $\gcd(30, 60) = 30$ 이다.

입력

입력은 한 개의 테스트 케이스로 이루어진다. 첫 줄에 수열의 정수 개수 $n$ ( $2 \le n \le 10^5$ )이 주어진다. 둘째 줄에는 수열을 이루는 양의 정수 $a_1, \dots, a_n$ 이 주어진다. 모든 값은 $10^5$ 를 넘지 않는다. 셋째 줄에는 구간의 개수 $q$ ( $q \le 10^5$ )가 주어진다. 이어지는 $q$ 개의 줄에는 각각 구간 $l_i$ , $r_i$ ( $1 \le l_i < r_i \le n$ )가 주어지며, 이는 $a_{l_i}$ 부터 $a_{r_i}$ 까지의 구간을 뜻한다.

출력

$q$ 개의 줄을 출력한다. $i$ 번째 줄에는 $l_i$ 부터 $r_i$ 까지 구간에 있는 모든 쌍의 최대공약수 중 최댓값을 출력한다.

예제2

예제 1

입력

6
10 20 30 40 50 60
3
1 6
2 5
4 5

예상 출력

30
20
10

예제 2

입력

10
13 2 35 4 13 2 5 1 7 4
5
1 4
4 10
3 8
3 9
1 10

예상 출력