문제 출처 : https://www.acmicpc.net/problem/14476

문제 정리

• N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것을 찾는 프로그램을 작성하시오.
• 이때, 최대공약수는 K의 약수가 되면 안 된다.
• 예를 들어, 정수 8, 12, 24, 36, 48에서 8을 빼면 나머지 12, 24, 36, 48의 최대공약수는 12가 되고, 12는 빠진 수 8의 약수가 아니기 때문에 정답이 될 수 있다. 이때, 다른 수를 빼도 최대공약수가 8보다 커질 수 없다.
• 하지만, 8, 12, 20, 32, 36의 경우에는 그 무엇을 빼더라도 나머지 수의 최대공약수가 K의 약수가 되기 때문에, 정답을 구할 수 없다.

문제 해결 방법

“생각보다 아주 아주 아주 아주 어려운 문제..”

딱 봐도 완전탐색을 할 수 없는 제한조건이 주어졌다. 그럼 어떻게 풀어야할지 상당히 고민이 된다.

이 문제는 누적합을 활용한 누적GCD를 사용하는 문제다.

간단하게 누적합을 설명하면,

• 방법1
  • N개의 수를 배열에 입력받고 i부터 j까지의 합을 입력이 올 때마다 계산해서 반환
  • 시간복잡도: O(n^2)
• 방법2
  • Prefix sum을 구해두고 sum(i)(처음부터 i까지의 합) - sum(j-1)(처음부터 j-1까지의 합)을 통해서 반환
  • 시간복잡도: O(n)

배열의 어떤 구간의 합을 구할 때 매번 입력을 받아서 구하면 최악의 경우 O(n^2)이지만 Prefix sum를 구해두면 O(n)만에 가능하다.

이 아이디어를 적용할 것이다.