시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB72311832.143%

문제

길이가 $N$인 양의 정수 수열 $A_1, A_2, \dots A_N$이 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • $L$ $R$ $K$ : $L \leq i \leq j \leq R$ 을 만족하는 모든 순서쌍 $\left(i, j\right)$에 대해 $\gcd(A_i, A_{i+1}, \dots , A_{j - 1}, A_j)$를 비내림차순으로 정렬했을 때 $K$번째로 나오는 수를 출력한다.

단, $\gcd(A_i) = A_i$로 정의한다.

길이가 $3$인 수열 $\left(1, 2, 4\right)$에 대해 $L = 1, R = 3$ 일 때 나올 수 있는 $\gcd$값은 $\left(1, 1, 1, 2, 2, 4\right)$이다. 이 때 $K=4$ 라면 $2$를 출력한다.

입력

첫째 줄에 수열의 길이 $N$이 주어진다. $\left(1 \leq N \leq 20\,000\right)$

둘째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. $\left(1 \leq A_i \leq 500\,000\right)$

셋째 줄에 쿼리의 개수 $Q$가 주어진다. $\left(1 \leq Q \leq 100\,000\right)$

넷째 줄부터 $Q$개의 줄에 걸쳐 쿼리 $L, R, K$가 한 줄에 하나씩 주어진다. $\left(1 \leq L \leq R \leq N, 1 \leq K \leq (R-L+1)(R-L+2)/2\right)$

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

8
1 2 4 8 72 27 9 3
10
1 1 1
2 2 1
1 2 3
2 7 3
2 7 10
2 7 15
2 7 21
1 8 1
1 8 18
1 8 36

예제 출력 1

1
2
2
1
2
8
72
1
2
72

출처

University > 성균관대학교 > 2023 성균관대학교 프로그래밍 경진대회 K번