정수론1

• 

  [c++] 백준-최대공약수 하나 빼기 ( 누적합, 정수론) 1. 문제 2. 입출력 및 예제 3. 문제 해설 하나를 뺐을 때 최대공약수가 최대가 되어야한다. 이 문제를 해결하기 위해서는 누적합의 개념을 적용해야한다. 사실 누적합은 누적해서 합을 구하는 것에만 쓰이는 개념은 아니다. 여태까지 나온 값들의 대표값을 의미하기도 한다. 그래서 세그먼트 트리나 인덱스드 트리로도 풀 수 있을 거 같은 문제였다. 핵심 아이디어는 다음과 같다. LtoR : 왼쪽서부터 최대 공약수를 구해 저장하는 배열 RtoL : 오른쪽서부터 최대 공약수를 구해 저장하는 배열 두 배열이 존재한다면 예제의 경우 다음과 같다. index 0 1 2 3 4 nums 8 12 24 36 48 LtoR 8 4 4 4 4 RtoL 12 12 12 12 48 세 가지의 경우로 나눌 수 있겠다. 먼저 맨 처음.. c++/알고리즘 2023. 2. 28.