관측소 측정값의 최대공약수
골드 I의견: 0
\(N\)개의 관측소가 일렬로 늘어서 있고, 각 관측소 \(i\)는 정수 측정값 \(a_i\)를 가진다.
다음 두 종류의 명령을 처리하라.
U i x: \(i\)번 관측소의 측정값을 \(x\)로 바꾼다.Q l r: 구간 \([l,r]\)에 속한 모든 측정값의 최대공약수 \(\gcd(a_l,\dots,a_r)\)를 구한다.
모든 Q 명령에 대한 답을 차례로 출력하라.
\(1 \le N, Q \le 100{,}000\), \(1 \le a_i, x \le 10^9\), \(1 \le l \le r \le N\), \(1 \le i \le N\).
첫째 줄에 \(N\)과 명령의 수 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1,\dots,a_N\)이 주어진다.
이후 \(Q\)개의 줄에 각 명령이 위 형식으로 주어진다.
각 Q 명령에 대해 한 줄에 하나씩 최대공약수를 출력한다.
6 5
12 18 24 6 9 15
Q 1 3
U 4 30
Q 4 6
Q 1 6
U 1 7
6
3
3\(Q\,1\,3\): \(\gcd(12,18,24)=6\). 갱신 후 \(Q\,4\,6\): \(\gcd(30,9,15)=3\). \(Q\,1\,6=\gcd(12,18,24,30,9,15)=3\).
4 3
8 8 8 8
Q 1 4
U 2 12
Q 1 2
8
4처음 \(Q\,1\,4=8\). \(2\)번째 값을 \(12\)로 바꾼 뒤 \(Q\,1\,2=\gcd(8,12)=4\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
관측소 측정값의 최대공약수
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
관측소 측정값의 최대공약수