펜윅 (1) 썸네일형 리스트형 [BOJ 12858] Range GCD https://www.acmicpc.net/problem/12858 12858번: Range GCD 첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어진다. i번째로 등장한 자연수는 수열의 i번째 www.acmicpc.net Tag : segment tree 문제요약 구간 업데이트(덧셈)가 있을 때 쿼리마다 구간의 gcd를 구하라. 풀이 a > b일 때 gcd(a, b) = gcd(a, a - b)임이 잘 알려져있습니다. 따라서 gcd(A[l], ... , A[r]) = gcd(A[l], A[l + 1] - A[l], ... , A[r] - A[r - 1])이 성립합니다. 세그먼트 트리의 각 노.. 이전 1 다음
