악보 화음 분석
골드 IV의견: 0
음악 분석가 소리는 \(N\)개의 음표를 일렬로 적은 악보를 갖고 있다. \(i\)번째 음표의 진동수는 양의 정수 \(a_i\)이다.
소리는 구간 \([l, r]\)에 포함된 음표들의 진동수의 최대공약수(GCD)를 구하면 그 구간이 '화음'을 이루는지 알 수 있다고 믿는다. 이 값이 클수록 음들이 잘 어우러진다.
\(Q\)번의 질문에 대해 각 구간의 진동수 GCD를 출력하여라.
- \(1 \le N, Q \le 200\,000\)
- \(1 \le l \le r \le N\)
- \(1 \le a_i \le 10^9\)
첫째 줄에 음표의 수 \(N\)과 질문의 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 음표의 진동수 \(a_1, a_2, \ldots, a_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 질문 \(l\), \(r\)이 주어진다. 구간 \([l, r]\)에 있는 음표들의 진동수 GCD를 구해야 한다.
\(Q\)개의 줄에 걸쳐 각 질문에 대한 GCD를 순서대로 출력한다.
5 3
12 18 24 9 6
1 3
1 5
4 5
6
3
3
\([1, 3]\)의 \(\gcd(12, 18, 24) = 6\)이다. \([1, 5]\)의 \(\gcd(12, 18, 24, 9, 6) = 3\)이다. \([4, 5]\)의 \(\gcd(9, 6) = 3\)이다.
3 3
7 14 21
1 1
1 3
2 3
7
7
7
단일 원소의 GCD는 원소 자체이므로 \([1,1]\)은 \(7\)이다. \([1,3]\)의 \(\gcd(7, 14, 21) = 7\)이다. \([2,3]\)의 \(\gcd(14, 21) = 7\)이다.
riseoj 작성
출처 Original
평가 및 의견
악보 화음 분석
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
악보 화음 분석